Smallest Substring With Identical Characters II - Video Solutions

Problem Overview: You are given a string and a limited number of modification operations. The goal is to minimize the length of the longest substring consisting of identical characters after applying at most k changes. The result is the smallest possible maximum run length achievable with those operations.

Approach 1: Linear Search on Maximum Run Length (Brute Force) (Time: O(n^2), Space: O(1))

Start by computing runs of identical characters in the string. Try every possible maximum allowed run length L from 1 to n. For each candidate L, iterate through all runs and calculate how many characters must be changed to break that run so no segment exceeds L. A run of length r requires roughly r / (L + 1) modifications because each modification splits the run. If the total required operations stay within k, the value is feasible. This approach is straightforward but too slow for large inputs because it checks every possible length.

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

The key observation: if a maximum run length L is achievable, then any value larger than L is also achievable. This monotonic property makes the problem ideal for binary search. Search the smallest feasible L in the range [1, n]. For each midpoint, scan the string and group consecutive identical characters. For a run of length r, compute the number of changes required to ensure each segment length is at most L. Each modification effectively breaks the run, so the required operations are r / (L + 1). Accumulate the operations across all runs and stop early if the count exceeds k.

The feasibility check is linear because it processes each character once while tracking run lengths. Combined with binary search, the total complexity becomes O(n log n), which handles large strings comfortably. The algorithm relies on simple iteration and greedy splitting of runs rather than complex data structures.

Recommended for interviews: Binary search on the answer with a greedy feasibility check is the expected solution. The brute-force attempt shows you understand the relationship between run length and required modifications, but the O(n log n) approach demonstrates strong problem-solving skills using monotonic properties and binary search over the answer space.