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.

Examples

Example 1

1
2
3
4

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

1
2
3
4

Input: s = "0000", numOps = 2
Output: 1
Explanation:  
By changing `s[0]` and `s[2]` to `'1'`, `s` becomes `"1010"`.

Example 3

1
2

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

Constraints

  • 1 <= n == s.length <= 1000
  • s consists only of '0' and '1'.
  • 0 <= numOps <= n

Solution

Method 1 – Binary Search on Substring Length

Intuition

We use binary search to find the minimum possible length of the longest substring with identical characters after performing at most numOps flips. For each candidate length, we check if it’s possible to achieve using the allowed operations.

Approach

  1. Apply binary search on possible substring lengths from 1 to n.
  2. For each candidate length mid, use an isValid function to check if it’s achievable:
    • If mid == 1, try to convert the string to alternating ‘0’ and ‘1’ patterns, counting mismatches for both starting characters.
    • If mid > 1, count the length of each run of identical characters. For each run longer than mid, calculate the number of flips needed to break it into smaller segments (using count // (mid + 1)).
  3. If a length is valid, update the answer and search for a smaller length; otherwise, search for a larger length.

Complexity

  • ⏰ Time complexity: O(n log n), due to binary search and linear scan for each candidate length.
  • 🧺 Space complexity: O(1), only constant extra space is used.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

class Solution {
public:
    int minLength(string s, int numOps) {
        int n = s.size(), left = 1, right = n, ans = n;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (isValid(s, numOps, mid)) {
                ans = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }
    bool checkAlternating(const string& s, int numOps, char startChar) {
        int opsNeeded = 0;
        char expected = startChar;
        for (char c : s) {
            if (c != expected) opsNeeded++;
            expected = (expected == '0') ? '1' : '0';
        }
        return opsNeeded <= numOps;
    }
    bool isValid(const string& s, int numOps, int mid) {
        if (mid == 1) {
            return checkAlternating(s, numOps, '0') || checkAlternating(s, numOps, '1');
        }
        int opsNeeded = 0, count = 1;
        for (int i = 1; i < s.size(); ++i) {
            if (s[i] == s[i-1]) {
                count++;
            } else {
                opsNeeded += count / (mid + 1);
                count = 1;
            }
        }
        opsNeeded += count / (mid + 1);
        return opsNeeded <= numOps;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

class Solution {
    public int minLength(String s, int numOps) {
        int n = s.length();
        int left = 1, right = n, ans = n;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (isValid(s, numOps, mid)) {
                ans = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }

    private boolean checkAlternating(String s, int numOps, char startChar) {
        int opsNeeded = 0;
        char expected = startChar;
        for (int i = 0; i < s.length(); ++i) {
            if (s.charAt(i) != expected) opsNeeded++;
            expected = (expected == '0') ? '1' : '0';
        }
        return opsNeeded <= numOps;
    }

    private boolean isValid(String s, int numOps, int mid) {
        if (mid == 1) {
            return checkAlternating(s, numOps, '0') || checkAlternating(s, numOps, '1');
        }
        int opsNeeded = 0, count = 1;
        for (int i = 1; i < s.length(); ++i) {
            if (s.charAt(i) == s.charAt(i-1)) {
                count++;
            } else {
                opsNeeded += count / (mid + 1);
                count = 1;
            }
        }
        opsNeeded += count / (mid + 1);
        return opsNeeded <= numOps;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

func minLength(s string, numOps int) int {
    n := len(s)
    left, right, ans := 1, n, n
    for left <= right {
        mid := left + (right-left)/2
        if isValid(s, numOps, mid) {
            ans = mid
            right = mid - 1
        } else {
            left = mid + 1
        }
    }
    return ans
}

func checkAlternating(s string, numOps int, startChar byte) bool {
    opsNeeded := 0
    expected := startChar
    for i := 0; i < len(s); i++ {
        if s[i] != expected {
            opsNeeded++
        }
        if expected == '0' {
            expected = '1'
        } else {
            expected = '0'
        }
    }
    return opsNeeded <= numOps
}

func isValid(s string, numOps, mid int) bool {
    if mid == 1 {
        return checkAlternating(s, numOps, '0') || checkAlternating(s, numOps, '1')
    }
    opsNeeded, count := 0, 1
    for i := 1; i < len(s); i++ {
        if s[i] == s[i-1] {
            count++
        } else {
            opsNeeded += count / (mid + 1)
            count = 1
        }
    }
    opsNeeded += count / (mid + 1)
    return opsNeeded <= numOps
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

class Solution {
    fun minLength(s: String, numOps: Int): Int {
        var left = 1
        var right = s.length
        var ans = s.length
        while (left <= right) {
            val mid = left + (right - left) / 2
            if (isValid(s, numOps, mid)) {
                ans = mid
                right = mid - 1
            } else {
                left = mid + 1
            }
        }
        return ans
    }
    private fun checkAlternating(s: String, numOps: Int, startChar: Char): Boolean {
        var opsNeeded = 0
        var expected = startChar
        for (c in s) {
            if (c != expected) opsNeeded++
            expected = if (expected == '0') '1' else '0'
        }
        return opsNeeded <= numOps
    }
    private fun isValid(s: String, numOps: Int, mid: Int): Boolean {
        if (mid == 1) {
            return checkAlternating(s, numOps, '0') || checkAlternating(s, numOps, '1')
        }
        var opsNeeded = 0
        var count = 1
        for (i in 1 until s.length) {
            if (s[i] == s[i-1]) {
                count++
            } else {
                opsNeeded += count / (mid + 1)
                count = 1
            }
        }
        opsNeeded += count / (mid + 1)
        return opsNeeded <= numOps
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

class Solution:
    def minLength(self, s: str, numOps: int) -> int:
        def check_alternating(s, numOps, start_char):
            ops_needed = 0
            expected = start_char
            for c in s:
                if c != expected:
                    ops_needed += 1
                expected = '1' if expected == '0' else '0'
            return ops_needed <= numOps
        def is_valid(s, numOps, mid):
            if mid == 1:
                return check_alternating(s, numOps, '0') or check_alternating(s, numOps, '1')
            ops_needed, count = 0, 1
            for i in range(1, len(s)):
                if s[i] == s[i-1]:
                    count += 1
                else:
                    ops_needed += count // (mid + 1)
                    count = 1
            ops_needed += count // (mid + 1)
            return ops_needed <= numOps
        n = len(s)
        left, right, ans = 1, n, n
        while left <= right:
            mid = left + (right - left) // 2
            if is_valid(s, numOps, mid):
                ans = mid
                right = mid - 1
            else:
                left = mid + 1
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

impl Solution {
    pub fn min_length(s: String, num_ops: i32) -> i32 {
        fn check_alternating(s: &str, num_ops: i32, start_char: char) -> bool {
            let mut ops_needed = 0;
            let mut expected = start_char;
            for c in s.chars() {
                if c != expected {
                    ops_needed += 1;
                }
                expected = if expected == '0' { '1' } else { '0' };
            }
            ops_needed <= num_ops
        }
        fn is_valid(s: &str, num_ops: i32, mid: i32) -> bool {
            if mid == 1 {
                return check_alternating(s, num_ops, '0') || check_alternating(s, num_ops, '1');
            }
            let mut ops_needed = 0;
            let mut count = 1;
            let s_bytes = s.as_bytes();
            for i in 1..s.len() {
                if s_bytes[i] == s_bytes[i-1] {
                    count += 1;
                } else {
                    ops_needed += count / (mid + 1);
                    count = 1;
                }
            }
            ops_needed += count / (mid + 1);
            ops_needed <= num_ops
        }
        let n = s.len() as i32;
        let mut left = 1;
        let mut right = n;
        let mut ans = n;
        while left <= right {
            let mid = left + (right - left) / 2;
            if is_valid(&s, num_ops, mid) {
                ans = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

class Solution {
    minLength(s: string, numOps: number): number {
        const checkAlternating = (s: string, numOps: number, startChar: string): boolean => {
            let opsNeeded = 0;
            let expected = startChar;
            for (let i = 0; i < s.length; i++) {
                if (s[i] !== expected) opsNeeded++;
                expected = expected === '0' ? '1' : '0';
            }
            return opsNeeded <= numOps;
        };
        const isValid = (s: string, numOps: number, mid: number): boolean => {
            if (mid === 1) {
                return checkAlternating(s, numOps, '0') || checkAlternating(s, numOps, '1');
            }
            let opsNeeded = 0, count = 1;
            for (let i = 1; i < s.length; i++) {
                if (s[i] === s[i-1]) {
                    count++;
                } else {
                    opsNeeded += Math.floor(count / (mid + 1));
                    count = 1;
                }
            }
            opsNeeded += Math.floor(count / (mid + 1));
            return opsNeeded <= numOps;
        };
        let left = 1, right = s.length, ans = s.length;
        while (left <= right) {
            const mid = left + Math.floor((right - left) / 2);
            if (isValid(s, numOps, mid)) {
                ans = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }
}