[LeetCode][Kotlin] 1888. Minimum Number of Flips to Make the Binary String Alternating

1888. Minimum Number of Flips to Make the Binary String Alternating

You are given a binary string s. You are allowed to perform two types of operations on the string in any sequence:

• Type-1: Remove the character at the start of the string s and append it to the end of the string.
• Type-2: Pick any character in s and flip its value, i.e., if its value is '0' it becomes '1' and vice-versa.

Return the minimum number of type-2 operations you need to perform such that s becomes alternating.

The string is called alternating if no two adjacent characters are equal.

• For example, the strings "010" and "1010" are alternating, while the string "0100" is not.

이진 문자열 s가 주어집니다. 문자열에 대해 임의의 순서로 두 가지 유형의 연산을 수행할 수 있습니다. 
- 유형-1: 문자열 s의 시작 부분에 있는 문자를 제거하고 문자열 끝에 추가합니다. 
- 유형-2: s에서 임의의 문자를 선택하여 값을 뒤집습니다. 즉, 값이 '0'이면 '1'이 되고 그 반대의 경우도 마찬가지입니다. 

s가 교대로 바뀌도록 수행해야 하는 최소 유형-2 연산 수를 반환합니다. 

두 개의 인접한 문자가 같지 않으면 문자열을 교대로 변경한다고 합니다. 
- 예를 들어 문자열 "010"과 "1010"은 교대로 변경되지만 문자열 "0100"은 교대로 변경되지 않습니다.

 

Example 1:

Input: s = "111000"

Output: 2

Explanation: Use the first operation two times to make s = "100011".

Then, use the second operation on the third and sixth elements to make s = "101010".

 

Example 2:

Input: s = "010"

Output: 0

Explanation: The string is already alternating.

 

Example 3:

Input: s = "1110"

Output: 1

Explanation: Use the second operation on the second element to make s = "1010".

 

Constraints:

• 1 <= s.length <= 10^5
• s[i] is either '0' or '1'.

---

코드 1

• Example 2 : s2 = 010010 / sb1 = 101010 / sb2 = 010101, 유형-2 → 유형-1

class Solution {
    fun minFlips(s: String): Int {
        val s2 = s + s
        val sb1 = StringBuilder()
        val sb2 = StringBuilder()

        for (i in s2.indices) {
            if (i % 2 == 0) {
                sb1.append('1')
                sb2.append('0')
            } else {
                sb1.append('0')
                sb2.append('1')
            }
        }

        val alt1 = sb1.toString()
        val alt2 = sb2.toString()
        var res = s2.length
        var diff1 = 0
        var diff2 = 0
        var l = 0

        for (r in 0 until s2.length) {
            if (alt1[r] != s2[r]) {
                diff1++
            }
            if (alt2[r] != s2[r]) {
                diff2++
            }

            if (r - l + 1 > s.length) {
                if (alt1[l] != s2[l]) {
                    diff1--
                }
                if (alt2[l] != s2[l]) {
                    diff2--
                }

                l++
            }

            if (r - l + 1 == s.length) {
                res = minOf(res, diff1, diff2)
            }
        }

        return res
    }
}

 

코드 2

class Solution {
    fun minFlips(s: String): Int {
        val n = s.length
        var diff1 = 0
        var diff2 = 0
        var res = n

        for (i in 0 until n * 2) {
            val sChar = s[i % n]
            val is0 = if (i % 2 == 0) '0' else '1'
            if (sChar != is0) {
                diff1++
            } else {
                diff2++
            }

            if (i >= n) {
                val firstCharInWindow = if ((i - n) % 2 == 0) '0' else '1'
                if (firstCharInWindow != s[i - n]) {
                    diff1--
                } else {
                    diff2--
                }

                res = minOf(res, diff1, diff2)
            }
        }

        return res
    }
}