Welcome to Subscribe On Youtube
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
(where0 <= i < n
) and flips[i]
. Ifs[i] == '1'
, changes[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
-
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; }