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

前往題目

想法

• Sliding window

思路

1. 原本的字串加上自己，這樣走過所有window等於把所有s的可能性都走過了
2. 另外準備兩個字串alt1和alt2，與s等長，是alternating binary string
3. sliding window從s最左邊開始，與alt1以及alt2相比，紀錄有多少個不同(diff)
4. 每次循環如果超過s的長度，縮小
5. 如果和s等長，紀錄diff最小值

這個思路簡潔明瞭，完美化解這題的所有障礙，寫起來也簡單，沒有什麼fancy的東西，就是把s變成s+s這個實在是神來一筆，其餘的就是sliding window的操作

Code

class Solution {
    public int minFlips(String s) {
        int n = s.length();
        s = s + s;
        StringBuilder alt1 = new StringBuilder("");
        StringBuilder alt2 = new StringBuilder("");

        // Build up alternating strings
        for (int i = 0; i < s.length(); ++i) {
            if (i % 2 == 1) {
                alt1.append("0");
            } else {
                alt1.append("1");
            }

            if (i % 2 == 1) {
                alt2.append("1");
            } else {
                alt2.append("0");
            }
        }

        int res = s.length();
        int diff1 = 0, diff2 = 0;
        int l = 0;
        
        // Sliding window
        for (int r = 0; r < s.length(); ++r) {
            if (s.charAt(r) != alt1.charAt(r)) {
                ++diff1;
            }
            if (s.charAt(r) != alt2.charAt(r)) {
                ++diff2;
            }

            // Window oversized, shrink it
            if ((r - l + 1) > n) {
                if (s.charAt(l) != alt1.charAt(l)) {
                    --diff1;
                }
                if (s.charAt(l) != alt2.charAt(l)) {
                    --diff2;
                }
                ++l;
            }

            // Update min number of flips
            if ((r - l + 1) == n) {
                res = Math.min(res, Math.min(diff1, diff2));
            }
        }

        return res;
    }
}