3398. Smallest Substring With Identical Characters I

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:

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 <= 1000
s consists only of '0' and '1'.
0 <= numOps <= n

Solutions

Solution 1

Thinking

We may flip at most \(\textit{numOps}\) bits to minimize the longest run of equal characters. With \(n \le 1000\) we binary-search the target length \(m\).

For \(m=1\) the string must become 0101... or 1010...; we take the closer pattern. For \(m>1\) a run of length \(k\) needs \(\lfloor k/(m+1) \rfloor\) flips.

\(m\) is feasible when the total flips are at most \(\textit{numOps}\). The smallest such \(m\) is the answer.

Python3JavaC++GoTypeScript

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)

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;
    }
}

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;
    }
};

func minLength(s string, numOps int) int {
    check := func(m int) bool {
        m++
        cnt := 0
        if m == 1 {
            t := "01"
            for i := range s {
                if s[i] == t[i&1] {
                    cnt++
                }
            }
            cnt = min(cnt, len(s)-cnt)
        } else {
            k := 0
            for i := range s {
                k++
                if i == len(s)-1 || s[i] != s[i+1] {
                    cnt += k / (m + 1)
                    k = 0
                }
            }
        }
        return cnt <= numOps
    }
    return 1 + sort.Search(len(s), func(m int) bool { return check(m) })
}

function minLength(s: string, numOps: number): number {
    const n = s.length;
    const check = (m: number): boolean => {
        let cnt = 0;
        if (m === 1) {
            const t = '01';
            for (let i = 0; i < n; ++i) {
                if (s[i] === t[i & 1]) {
                    ++cnt;
                }
            }
            cnt = Math.min(cnt, n - cnt);
        } else {
            let k = 0;
            for (let i = 0; i < n; ++i) {
                ++k;
                if (i === n - 1 || s[i] !== s[i + 1]) {
                    cnt += Math.floor(k / (m + 1));
                    k = 0;
                }
            }
        }
        return cnt <= numOps;
    };
    let [l, r] = [1, n];
    while (l < r) {
        const mid = (l + r) >> 1;
        if (check(mid)) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    return l;
}

3398. Smallest Substring With Identical Characters I

Description

Solutions

Solution 1

Comments