Welcome to Subscribe On Youtube

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:

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

Solutions

Solution 1

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

All Problems

All Solutions