Smallest Substring With Identical Characters I - Video Solutions

Problem Overview: You’re given a string and a limited number of character modifications. The goal is to minimize the length of the longest substring consisting of identical characters after performing at most k changes. Instead of directly constructing the final string, treat it as an optimization problem: what is the smallest possible maximum run length you can achieve?

Approach 1: Enumerate Possible Maximum Length (Brute Force) (Time: O(n^2), Space: O(1))

Try every possible maximum substring length L from 1 to n. For each candidate length, scan the string and measure contiguous runs of identical characters. If a run has length r, you must break it so no segment exceeds L. That requires floor(r / (L + 1)) character changes because every L+1 characters you need a modification to split the run. Sum the required changes across all runs and check if the total is ≤ k. This works but testing every L makes it too slow for large inputs.

Approach 2: Binary Search on the Answer (Optimal) (Time: O(n log n), Space: O(1))

The key observation: if a maximum run length L is achievable with ≤ k changes, then any value larger than L is also achievable. This monotonic property allows binary search over the answer range [1, n]. For each midpoint L, perform a single pass through the string and compute how many changes are required to break runs longer than L. The run counting step is simple array/enumeration: iterate through the string, track the current run length, and apply floor(run / (L + 1)) to accumulate needed operations. If the total exceeds k, reduce the search range; otherwise try a smaller L.

This approach converts a difficult string modification problem into a decision problem checked in linear time. Binary search reduces the candidate space quickly, while the run-length calculation keeps each check efficient.

Recommended for interviews: Start by describing the brute-force enumeration to show you understand how modifications break character runs. Then move to binary search on the maximum allowed substring length. Interviewers typically expect the O(n log n) solution because it demonstrates recognizing monotonic constraints and combining run-length enumeration with binary search.