Smallest Substring With Identical Characters II

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

Examples

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: "0000", numOps = 2
Output: 1
Explanation:  
By changing `s[0]` and `s[2]` to `'1'`, `s` becomes `"1010"`.

Example 3

Input: "0101", numOps = 0
Output: 1

Constraints

• 1 <= n == s.length <= 10^5
• s consists only of '0' and '1'.
• 0 <= numOps <= n

Solution

Method 1 – Binary Search + Sliding Window

Intuition

To minimize the length of the longest substring of identical characters after at most numOps flips, we can use binary search on the answer. For each possible length, we check if we can break all runs of length > mid by flipping at most numOps bits. This can be checked efficiently using a sliding window.

Approach

1. Set left = 1, right = n (length of s).
2. For each mid in binary search:
   • For both '0' and '1', use a sliding window of size mid to check if every window can be made all the same with at most numOps flips.
   • If possible for either, try smaller mid; else, try larger mid.
3. Return the minimal mid for which it is possible.

Code

C++

class Solution {
public:
    int minLength(string s, int k) {
        int n = s.size(), ans = n;
        auto check = [&](int m, char ch) {
            int cnt = 0;
            for (int i = 0; i < m; ++i) cnt += s[i] != ch;
            if (cnt <= k) return true;
            for (int i = m; i < n; ++i) {
                cnt += s[i] != ch;
                cnt -= s[i-m] != ch;
                if (cnt <= k) return true;
            }
            return false;
        };
        int l = 1, r = n;
        while (l <= r) {
            int m = (l + r) / 2;
            if (check(m, '0') || check(m, '1')) { ans = m; r = m - 1; }
            else l = m + 1;
        }
        return ans;
    }
};

Go

func minLength(s string, k int) int {
    n, ans := len(s), len(s)
    check := func(m int, ch byte) bool {
        cnt := 0
        for i := 0; i < m; i++ { if s[i] != ch { cnt++ } }
        if cnt <= k { return true }
        for i := m; i < n; i++ {
            if s[i] != ch { cnt++ }
            if s[i-m] != ch { cnt-- }
            if cnt <= k { return true }
        }
        return false
    }
    l, r := 1, n
    for l <= r {
        m := (l + r) / 2
        if check(m, '0') || check(m, '1') { ans = m; r = m - 1 } else { l = m + 1 }
    }
    return ans
}

Java

class Solution {
    public int minLength(String s, int k) {
        int n = s.length(), ans = n;
        int l = 1, r = n;
        while (l <= r) {
            int m = (l + r) / 2;
            if (check(s, m, k, '0') || check(s, m, k, '1')) { ans = m; r = m - 1; }
            else l = m + 1;
        }
        return ans;
    }
    private boolean check(String s, int m, int k, char ch) {
        int cnt = 0, n = s.length();
        for (int i = 0; i < m; ++i) if (s.charAt(i) != ch) cnt++;
        if (cnt <= k) return true;
        for (int i = m; i < n; ++i) {
            if (s.charAt(i) != ch) cnt++;
            if (s.charAt(i-m) != ch) cnt--;
            if (cnt <= k) return true;
        }
        return false;
    }
}

Kotlin

class Solution {
    fun minLength(s: String, k: Int): Int {
        val n = s.length
        var ans = n
        fun check(m: Int, ch: Char): Boolean {
            var cnt = 0
            for (i in 0 until m) if (s[i] != ch) cnt++
            if (cnt <= k) return true
            for (i in m until n) {
                if (s[i] != ch) cnt++
                if (s[i-m] != ch) cnt--
                if (cnt <= k) return true
            }
            return false
        }
        var l = 1; var r = n
        while (l <= r) {
            val m = (l + r) / 2
            if (check(m, '0') || check(m, '1')) { ans = m; r = m - 1 }
            else l = m + 1
        }
        return ans
    }
}

Python

class Solution:
    def minLength(self, s: str, k: int) -> int:
        n, ans = len(s), len(s)
        def check(m: int, ch: str) -> bool:
            cnt = sum(1 for i in range(m) if s[i] != ch)
            if cnt <= k: return True
            for i in range(m, n):
                cnt += s[i] != ch
                cnt -= s[i-m] != ch
                if cnt <= k: return True
            return False
        l, r = 1, n
        while l <= r:
            m = (l + r) // 2
            if check(m, '0') or check(m, '1'):
                ans = m
                r = m - 1
            else:
                l = m + 1
        return ans

Rust

impl Solution {
    pub fn min_length(s: String, k: i32) -> i32 {
        let n = s.len();
        let s = s.as_bytes();
        let mut ans = n as i32;
        let mut l = 1;
        let mut r = n as i32;
        let check = |m: i32, ch: u8| -> bool {
            let mut cnt = 0;
            for i in 0..m { if s[i as usize] != ch { cnt += 1; } }
            if cnt <= k { return true; }
            for i in m..n as i32 {
                if s[i as usize] != ch { cnt += 1; }
                if s[(i-m) as usize] != ch { cnt -= 1; }
                if cnt <= k { return true; }
            }
            false
        };
        while l <= r {
            let m = (l + r) / 2;
            if check(m, b'0') || check(m, b'1') { ans = m; r = m - 1; }
            else { l = m + 1; }
        }
        ans
    }
}

TypeScript

class Solution {
    minLength(s: string, k: number): number {
        const n = s.length;
        let ans = n;
        function check(m: number, ch: string): boolean {
            let cnt = 0;
            for (let i = 0; i < m; ++i) if (s[i] !== ch) cnt++;
            if (cnt <= k) return true;
            for (let i = m; i < n; ++i) {
                if (s[i] !== ch) cnt++;
                if (s[i-m] !== ch) cnt--;
                if (cnt <= k) return true;
            }
            return false;
        }
        let l = 1, r = n;
        while (l <= r) {
            const m = (l + r) >> 1;
            if (check(m, '0') || check(m, '1')) { ans = m; r = m - 1; }
            else l = m + 1;
        }
        return ans;
    }
}

Complexity

• ⏰ Time complexity: O(n log n), where n is the length of s. Each binary search step takes O(n) for sliding window, and there are O(log n) steps.
• 🧺 Space complexity: O(1), only a constant number of variables are used.