Smallest Substring With Identical Characters II

Hard

#3020Time: O(N * K * log N), where N is the length of the string and K is the candidate length from the binary search. In the worst case, K can be on the order of N, leading to O(N^2 * log N).Space: O(N) for the DP arrays and prefix sums.

Algorithms

Binary Search

Data structures

String

Prompt

You are given a binary string s of length n and an integer numOps.

You are allowed to perform the following operation on s at most numOps times:

Select any index i (where 0 <= i < n) and flip s[i]. If s[i] == '1', change s[i] to '0' and vice versa.

You need to minimize the length of the longest substring of s such that all the characters in the substring are identical.

Return the minimum length after the operations.

Example 1:

Input: s = "000001", numOps = 1

Output: 2

Explanation:

By changing s[2] to '1', s becomes "001001". The longest substrings with identical characters are s[0..1] and s[3..4].

Example 2:

Input: s = "0000", numOps = 2

Output: 1

Explanation:

By changing s[0] and s[2] to '1', s becomes "1010".

Example 3:

Input: s = "0101", numOps = 0

Output: 1

Constraints:

1 <= n == s.length <= 10⁵
s consists only of '0' and '1'.
0 <= numOps <= n

Approaches

2 approaches with complexity analysis and trade-offs.

The problem asks to minimize a maximum value (the length of the longest identical-character substring), which suggests that we can binary search on the answer. Let's say we want to check if it's possible to make the maximum length of such substrings at most k.

If we can determine this for any given k (let's call this function check(k)), we can binary search for the smallest k in the range [1, n] for which check(k) is true. The core of this approach is to implement check(k) efficiently.

Algorithm

Binary search for the answer k (minimum possible length of the longest run) in the range [1, n].
For each k during the binary search, call a helper function check(k).
check(k) calculates the minimum flips needed to ensure all runs of identical characters are of length at most k.
Inside check(k), use dynamic programming. Let dp[i][c] be the minimum flips for prefix s[0...i] to be valid, with s[i] becoming character c.
The transition for dp[i][c] involves looking back at the last position p of character 1-c. The run of c's can be at most k long, so i-p <= k. We iterate through all valid p in [i-k, i-1] to find the minimum cost.
Precompute prefix sums of 0s and 1s to quickly calculate the number of flips needed for a substring.
The total cost for check(k) is min(dp[n-1][0], dp[n-1][1]). If this is <= numOps, check(k) is true.
If check(k) is true, we try a smaller k; otherwise, we need a larger k.

Walkthrough

The check(k) function determines the minimum number of flips required to ensure no substring of identical characters is longer than k. If this minimum number is within numOps, then it's possible.

We can solve this using dynamic programming. Let dp[i][c] be the minimum number of flips required for the prefix s[0...i] such that all identical-character runs have a length of at most k, and the character at index i is transformed to c (where c is '0' or '1').

To compute dp[i][c], we consider that if s[i] becomes c, it must be the end of a run of c's of some length l where 1 <= l <= k. This means the character at i-l must be 1-c. The cost is the sum of the flips for the prefix s[0...i-l] ending in 1-c, plus the flips needed to make s[i-l+1...i] all c's.

This leads to the recurrence: dp[i][c] = min_{max(-1, i-k) <= p < i} (dp[p][1-c] + cost_to_make_substring(p+1, i, c)) where dp[-1][c] = 0. The cost of making a substring can be found using prefix sums of 0s and 1s in the original string. In this approach, we compute the min over the window [i-k, i-1] with a simple loop, leading to an O(k) transition.

1class Solution {2    public int smallestSubstring(String s, int numOps) {3        int n = s.length();4        int low = 1, high = n, ans = n;5        while (low <= high) {6            int mid = low + (high - low) / 2;7            if (check(mid, s, numOps)) {8                ans = mid;9                high = mid - 1;10            } else {11                low = mid + 1;12            }13        }14        return ans;15    }16 17    private boolean check(int k, String s, int numOps) {18        int n = s.length();19        int[] ones = new int[n + 1];20        for (int i = 0; i < n; i++) {21            ones[i + 1] = ones[i] + (s.charAt(i) - '0');22        }23 24        int[] dp0 = new int[n];25        int[] dp1 = new int[n];26 27        for (int i = 0; i < n; i++) {28            // Calculate dp[i][0]29            int minCost0 = Integer.MAX_VALUE;30            for (int p = i - 1; p >= i - k && p >= -1; p--) {31                int prevCost = (p == -1) ? 0 : dp1[p];32                int flips = (ones[i + 1] - ones[p + 1]);33                minCost0 = Math.min(minCost0, prevCost + flips);34            }35            dp0[i] = minCost0;36 37            // Calculate dp[i][1]38            int minCost1 = Integer.MAX_VALUE;39            for (int p = i - 1; p >= i - k && p >= -1; p--) {40                int prevCost = (p == -1) ? 0 : dp0[p];41                int zerosInSubstring = (i - p) - (ones[i + 1] - ones[p + 1]);42                minCost1 = Math.min(minCost1, prevCost + zerosInSubstring);43            }44            dp1[i] = minCost1;45        }46 47        return Math.min(dp0[n - 1], dp1[n - 1]) <= numOps;48    }49}

Complexity

Time

O(N * K * log N), where N is the length of the string and K is the candidate length from the binary search. In the worst case, K can be on the order of N, leading to O(N^2 * log N).

Space

O(N) for the DP arrays and prefix sums.

Trade-offs

Pros

The binary search framework correctly narrows down the search space for the answer.
The DP formulation correctly solves the subproblem of finding the minimum flips for a given k.

Cons

The check(k) function has a time complexity of O(n*k) because of the nested loop in the DP transition.
The overall time complexity of O(n*k*log n) can be up to O(n^2*log n), which is too slow for the given constraints (n <= 10^5).

This approach builds upon the previous one. We still use binary search on the answer k. The key improvement is optimizing the check(k) function from O(n*k) to O(n).

The DP transition involves finding a minimum value over a sliding window. Instead of using a linear scan which takes O(k) time, we can use a more advanced data structure, a double-ended queue (deque), to find this minimum in amortized O(1) time.

Algorithm

The overall structure is the same: binary search for the answer k.
The check(k) function uses the same DP state and recurrence as the previous approach.
The key difference is the implementation of the DP transition.
Rewrite the recurrence to isolate the term that needs to be minimized over the sliding window: dp[i][c] = prefix_sum_cost + min_{p in window} (dp[p][1-c] - prefix_sum_cost_at_p).
Maintain two deques, one for each target character ('0' and '1'). Each deque will store pairs of (value, index) to find the minimum value in the sliding window efficiently.
For each i from 0 to n-1: a. Remove elements from the front of the deques whose indices are no longer in the window [i-k, i-1]. b. The minimum value required for the DP transition is now at the front of the appropriate deque. Calculate dp[i][0] and dp[i][1] in O(1) time. c. Add the new values for index i to the back of the deques, maintaining the monotonically increasing property of values in the deque.
This makes the check(k) function O(n).

Walkthrough

The DP recurrence remains the same: dp[i][c] = min_{max(-1, i-k) <= p < i} (dp[p][1-c] + cost_to_make_substring(p+1, i, c))

We can rewrite the transition to isolate the part that depends on p: dp[i][0] = (cost to make s[...i] all 0s) + min_{...} (dp[p][1] - cost to make s[...p] all 0s) More precisely: dp[i][0] = num_ones[i+1] + min_{max(-1, i-k) <= p < i} (dp[p][1] - num_ones[p+1]) dp[i][1] = num_zeros[i+1] + min_{max(-1, i-k) <= p < i} (dp[p][0] - num_zeros[p+1])

The min term is a classic sliding window minimum problem. As we iterate i from 0 to n-1, the window for p, [i-k, i-1], slides forward. We can maintain two deques, one for character '0' and one for '1', to keep track of the minimum values of (dp[p][c] - prefix_sum[p+1]) within the current window. Each element is pushed and popped from the deque at most once, making the DP transition amortized O(1).

This optimization reduces the complexity of check(k) to O(n), and the overall complexity to O(n log n).

1import java.util.ArrayDeque;2import java.util.Deque;3 4class Solution {5    // A simple Pair class, or use int[2]6    class Pair {7        int key, value;8        Pair(int key, int value) {9            this.key = key;10            this.value = value;11        }12        public int getKey() { return key; }13        public int getValue() { return value; }14    }15 16    public int smallestSubstring(String s, int numOps) {17        int n = s.length();18        int low = 1, high = n, ans = n;19        while (low <= high) {20            int mid = low + (high - low) / 2;21            if (check(mid, s, numOps)) {22                ans = mid;23                high = mid - 1;24            } else {25                low = mid + 1;26            }27        }28        return ans;29    }30 31    private boolean check(int k, String s, int numOps) {32        int n = s.length();33        int[] ones = new int[n + 1];34        int[] zeros = new int[n + 1];35        for (int i = 0; i < n; i++) {36            ones[i + 1] = ones[i] + (s.charAt(i) - '0');37            zeros[i + 1] = zeros[i] + (s.charAt(i) == '0' ? 1 : 0);38        }39 40        int[] dp0 = new int[n];41        int[] dp1 = new int[n];42 43        Deque<Pair> dq0 = new ArrayDeque<>();44        Deque<Pair> dq1 = new ArrayDeque<>();45 46        // Base case for p = -147        dq0.add(new Pair(0 - zeros[0], -1)); // dp[-1][0] - zeros[0]48        dq1.add(new Pair(0 - ones[0], -1));  // dp[-1][1] - ones[0]49 50        for (int i = 0; i < n; i++) {51            // Remove indices outside the window [i-k, i-1]52            while (!dq0.isEmpty() && dq0.peekFirst().getValue() < i - k) {53                dq0.pollFirst();54            }55            while (!dq1.isEmpty() && dq1.peekFirst().getValue() < i - k) {56                dq1.pollFirst();57            }58 59            // Calculate dp[i][0] and dp[i][1]60            dp0[i] = ones[i + 1] + dq1.peekFirst().getKey();61            dp1[i] = zeros[i + 1] + dq0.peekFirst().getKey();62 63            // Add current state to deques for future calculations64            int val_dq0 = dp0[i] - zeros[i + 1];65            while (!dq0.isEmpty() && dq0.peekLast().getKey() >= val_dq0) {66                dq0.pollLast();67            }68            dq0.addLast(new Pair(val_dq0, i));69 70            int val_dq1 = dp1[i] - ones[i + 1];71            while (!dq1.isEmpty() && dq1.peekLast().getKey() >= val_dq1) {72                dq1.pollLast();73            }74            dq1.addLast(new Pair(val_dq1, i));75        }76 77        return Math.min(dp0[n - 1], dp1[n - 1]) <= numOps;78    }79}

Complexity

Time

O(N log N), where N is the length of the string. The binary search takes O(log N) iterations, and each `check(k)` call takes O(N) time.

Space

O(N) for the DP arrays, prefix sums, and the deques.

Trade-offs

Pros

Highly efficient, with a time complexity that passes the given constraints.
It's a standard and powerful pattern: binary search on the answer combined with an efficient DP using a sliding window optimization.

Cons

The logic is more complex to understand and implement correctly, especially the sliding window minimum part with deques.

Solutions

Solution

1class Solution { private char [] s ; private int numOps ; public int minLength ( String s , int numOps ) { this . numOps = numOps ; this . s = s . toCharArray (); int l = 1 , r = s . length (); while ( l < r ) { int mid = ( l + r ) >> 1 ; if ( check ( mid )) { r = mid ; } else { l = mid + 1 ; } } return l ; } private boolean check ( int m ) { int cnt = 0 ; if ( m == 1 ) { char [] t = { '0' , '1' }; for ( int i = 0 ; i < s . length ; ++ i ) { if ( s [ i ] == t [ i & 1 ]) { ++ cnt ; } } cnt = Math . min ( cnt , s . length - cnt ); } else { int k = 0 ; for ( int i = 0 ; i < s . length ; ++ i ) { ++ k ; if ( i == s . length - 1 || s [ i ] != s [ i + 1 ]) { cnt += k / ( m + 1 ); k = 0 ; } } } return cnt <= numOps ; } }

1class Solution { public: int minLength ( string s , int numOps ) { int n = s . size (); auto check = [ & ]( int m ) { int cnt = 0 ; if ( m == 1 ) { string t = "01" ; for ( int i = 0 ; i < n ; ++ i ) { if ( s [ i ] == t [ i & 1 ]) { ++ cnt ; } } cnt = min ( cnt , n - cnt ); } else { int k = 0 ; for ( int i = 0 ; i < n ; ++ i ) { ++ k ; if ( i == n - 1 || s [ i ] != s [ i + 1 ]) { cnt += k / ( m + 1 ); k = 0 ; } } } return cnt <= numOps ; }; int l = 1 , r = n ; while ( l < r ) { int mid = ( l + r ) >> 1 ; if ( check ( mid )) { r = mid ; } else { l = mid + 1 ; } } return l ; } };

1class Solution:2    def minLength(self, s: str, numOps: int) -> int: def check(m: int) -> bool: cnt = 0 if m == 1: t = "01" cnt = sum(c == t[i & 1] for i, c in enumerate(s)) cnt = min(cnt, n - cnt) else: k = 0 for i, c in enumerate(s): k += 1 if i == len(s) - 1 or c != s[i + 1]: cnt += k // (m + 1) k = 0 return cnt <= numOps n = len(s) return bisect_left(range(n), True, lo=1, key=check)

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem