3399. Smallest Substring With Identical Characters II

Posted on Edited on In

3399. Smallest Substring With Identical Characters II

Description

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:

1
2
3
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
Input: s = "0000", numOps = 2

Output: 1

Explanation:

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

Example 3:

1
2
3
Input: s = "0101", numOps = 0

Output: 1

Constraints:

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

Hints/Notes

Solution

Language: C++

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 left = 0, right = s.size();
        // we can always achieve right len, check(right) is always true
        // while check left is always false
        while (left + 1 < right) {
            int mid = (left + right) / 2;
            // if check(), it means we can achieve mid size
            // with number of op <= numOps
            if (!check(mid, s, numOps)) {
                left = mid;
            } else {
                right = mid;
            }
        }
        return right;
    }

    bool check(int len, string& s, int numOps) {
        int n = s.size(), res = 0;
        if (len == 1) {
            int cur = 0;
            for (char& c : s) {
                if (cur != c - '0') {
                    res++;
                }
                cur ^= 1;
            }
            return min(res, n - res) <= numOps;
        }
        for (int i = 0; i < n; ) {
            int start = i;
            while (i < n && s[i] == s[start]) {
                i++;
            }
            res += (i - start) / (len + 1);
        }
        return res <= numOps;
    }
};