LeetCode in Kotlin

3398. Smallest Substring With Identical Characters I

Hard

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

Solution

class Solution {
    fun minLength(s: String, ops: Int): Int {
        val arr2 = s.toCharArray()
        var q = '0'.code
        var w = '1'.code
        var p1 = ops
        var p2 = ops
        for (i in 0..<s.length) {
            if (arr2[i].code != q) {
                p1--
            }
            if (arr2[i].code != w) {
                p2--
            }
            if (q == '0'.code) {
                q = '1'.code
            } else {
                q = '0'.code
            }
            if (w == '0'.code) {
                w = '1'.code
            } else {
                w = '0'.code
            }
        }
        if (p1 >= 0 || p2 >= 0) {
            return 1
        }
        var low = 2
        var high = s.length
        var ans = 0
        val n = s.length
        while (low <= high) {
            val mid = (low + high) / 2
            val arr = s.toCharArray()
            var p = ops
            var c = 1
            for (i in 1..<n) {
                if (arr[i] == arr[i - 1]) {
                    c++
                } else {
                    c = 1
                }
                if (c > mid) {
                    if (arr[i - 1] == '0') {
                        arr[i - 1] = '1'
                    } else {
                        arr[i - 1] = '0'
                    }
                    p--
                    c = 0
                }
            }
            if (p < 0) {
                low = mid + 1
            } else {
                ans = mid
                high = mid - 1
            }
        }
        return ans
    }
}

This site is open source. Improve this page.