# Smallest Substring With Identical Characters II
**Difficulty:** HARD
[External](https://leetcode.com/problems/smallest-substring-with-identical-characters-ii)
Canonical: https://scaleengineer.com/dsa/problems/smallest-substring-with-identical-characters-ii
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** String
---
## Problem
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 <= 105`
* `s` consists only of `'0'` and `'1'`.
* `0 <= numOps <= n`

# Approaches
## Binary Search with Dynamic Programming
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.
**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.
**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`).
### Explanation
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 `0`s and `1`s 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.

```java
class Solution {
    public int smallestSubstring(String s, int numOps) {
        int n = s.length();
        int low = 1, high = n, ans = n;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (check(mid, s, numOps)) {
                ans = mid;
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return ans;
    }

    private boolean check(int k, String s, int numOps) {
        int n = s.length();
        int[] ones = new int[n + 1];
        for (int i = 0; i < n; i++) {
            ones[i + 1] = ones[i] + (s.charAt(i) - '0');
        }

        int[] dp0 = new int[n];
        int[] dp1 = new int[n];

        for (int i = 0; i < n; i++) {
            // Calculate dp[i][0]
            int minCost0 = Integer.MAX_VALUE;
            for (int p = i - 1; p >= i - k && p >= -1; p--) {
                int prevCost = (p == -1) ? 0 : dp1[p];
                int flips = (ones[i + 1] - ones[p + 1]);
                minCost0 = Math.min(minCost0, prevCost + flips);
            }
            dp0[i] = minCost0;

            // Calculate dp[i][1]
            int minCost1 = Integer.MAX_VALUE;
            for (int p = i - 1; p >= i - k && p >= -1; p--) {
                int prevCost = (p == -1) ? 0 : dp0[p];
                int zerosInSubstring = (i - p) - (ones[i + 1] - ones[p + 1]);
                minCost1 = Math.min(minCost1, prevCost + zerosInSubstring);
            }
            dp1[i] = minCost1;
        }

        return Math.min(dp0[n - 1], dp1[n - 1]) <= numOps;
    }
}
```
### Algorithm
1. Binary search for the answer `k` (minimum possible length of the longest run) in the range `[1, n]`.
2. For each `k` during the binary search, call a helper function `check(k)`.
3. `check(k)` calculates the minimum flips needed to ensure all runs of identical characters are of length at most `k`.
4. 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`.
5. 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.
6. Precompute prefix sums of `0`s and `1`s to quickly calculate the number of flips needed for a substring.
7. The total cost for `check(k)` is `min(dp[n-1][0], dp[n-1][1])`. If this is `<= numOps`, `check(k)` is true.
8. If `check(k)` is true, we try a smaller `k`; otherwise, we need a larger `k`.

## Binary Search with Optimized DP using Sliding Window Minimum
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.
**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.
**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.
### Explanation
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)`. 

```java
import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    // A simple Pair class, or use int[2]
    class Pair {
        int key, value;
        Pair(int key, int value) {
            this.key = key;
            this.value = value;
        }
        public int getKey() { return key; }
        public int getValue() { return value; }
    }

    public int smallestSubstring(String s, int numOps) {
        int n = s.length();
        int low = 1, high = n, ans = n;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (check(mid, s, numOps)) {
                ans = mid;
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return ans;
    }

    private boolean check(int k, String s, int numOps) {
        int n = s.length();
        int[] ones = new int[n + 1];
        int[] zeros = new int[n + 1];
        for (int i = 0; i < n; i++) {
            ones[i + 1] = ones[i] + (s.charAt(i) - '0');
            zeros[i + 1] = zeros[i] + (s.charAt(i) == '0' ? 1 : 0);
        }

        int[] dp0 = new int[n];
        int[] dp1 = new int[n];

        Deque<Pair> dq0 = new ArrayDeque<>();
        Deque<Pair> dq1 = new ArrayDeque<>();

        // Base case for p = -1
        dq0.add(new Pair(0 - zeros[0], -1)); // dp[-1][0] - zeros[0]
        dq1.add(new Pair(0 - ones[0], -1));  // dp[-1][1] - ones[0]

        for (int i = 0; i < n; i++) {
            // Remove indices outside the window [i-k, i-1]
            while (!dq0.isEmpty() && dq0.peekFirst().getValue() < i - k) {
                dq0.pollFirst();
            }
            while (!dq1.isEmpty() && dq1.peekFirst().getValue() < i - k) {
                dq1.pollFirst();
            }

            // Calculate dp[i][0] and dp[i][1]
            dp0[i] = ones[i + 1] + dq1.peekFirst().getKey();
            dp1[i] = zeros[i + 1] + dq0.peekFirst().getKey();

            // Add current state to deques for future calculations
            int val_dq0 = dp0[i] - zeros[i + 1];
            while (!dq0.isEmpty() && dq0.peekLast().getKey() >= val_dq0) {
                dq0.pollLast();
            }
            dq0.addLast(new Pair(val_dq0, i));

            int val_dq1 = dp1[i] - ones[i + 1];
            while (!dq1.isEmpty() && dq1.peekLast().getKey() >= val_dq1) {
                dq1.pollLast();
            }
            dq1.addLast(new Pair(val_dq1, i));
        }

        return Math.min(dp0[n - 1], dp1[n - 1]) <= numOps;
    }
}
```
### Algorithm
1. The overall structure is the same: binary search for the answer `k`.
2. The `check(k)` function uses the same DP state and recurrence as the previous approach.
3. The key difference is the implementation of the DP transition.
4. 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)`.
5. 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.
6. 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.
7. This makes the `check(k)` function `O(n)`.

# Solutions
### Java

```java
class 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 ; } }
```

### CPP

```cpp
class 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 ; } };
```

### Python

```python
class Solution:
    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)

```