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

/**
 * Problem: LeetCode 1888 - Minimum Number of Flips to Make the Binary String Alternating
 * Difficulty: Medium
 * Language: Java
 * Author: CodeByTushu
 */
class Solution {
    public int minFlips(String s) {
        int n = s.length();
        int diff1 = 0; // Mismatches with alternating pattern starting with '0'
        int diff2 = 0; // Mismatches with alternating pattern starting with '1'
        int minFlips = n;

        // Simulate sliding window of length n over virtual doubled string (s + s)
        for (int i = 0; i < 2 * n; i++) {
            char curr = s.charAt(i % n);
            char target1 = (i % 2 == 0) ? '0' : '1';
            char target2 = (i % 2 == 0) ? '1' : '0';

            if (curr != target1) diff1++;
            if (curr != target2) diff2++;

            // Shrink window if it exceeds length n
            if (i >= n) {
                char out = s.charAt((i - n) % n);
                char outTarget1 = ((i - n) % 2 == 0) ? '0' : '1';
                char outTarget2 = ((i - n) % 2 == 0) ? '1' : '0';

                if (out != outTarget1) diff1--;
                if (out != outTarget2) diff2--;
            }

            // Once window reaches size n, record the minimum flips
            if (i >= n - 1) {
                minFlips = Math.min(minFlips, Math.min(diff1, diff2));
            }
        }

        return minFlips;
    }
}

"""
Problem: LeetCode 1888 - Minimum Number of Flips to Make the Binary String Alternating
Difficulty: Medium
Language: Python
Author: CodeByTushu
"""
class Solution:
    def minFlips(self, s: str) -> int:
        n = len(s)
        diff1 = 0  # Mismatches with pattern starting with '0' ("010101...")
        diff2 = 0  # Mismatches with pattern starting with '1' ("101010...")
        min_flips = n

        # Slide a window of length n over virtual doubled string s + s
        for i in range(2 * n):
            curr = s[i % n]
            t1 = '0' if i % 2 == 0 else '1'
            t2 = '1' if i % 2 == 0 else '0'

            if curr != t1:
                diff1 += 1
            if curr != t2:
                diff2 += 1

            # Remove character going out of window
            if i >= n:
                out = s[(i - n) % n]
                out_t1 = '0' if (i - n) % 2 == 0 else '1'
                out_t2 = '1' if (i - n) % 2 == 0 else '0'

                if out != out_t1:
                    diff1 -= 1
                if out != out_t2:
                    diff2 -= 1

            # Window of length n reached
            if i >= n - 1:
                min_flips = min(min_flips, diff1, diff2)

        return min_flips

/**
 * Problem: LeetCode 1888 - Minimum Number of Flips to Make the Binary String Alternating
 * Difficulty: Medium
 * Language: C++
 * Author: CodeByTushu
 */
#include <string>
#include <algorithm>

using namespace std;

class Solution {
public:
    int minFlips(string s) {
        int n = s.length();
        int diff1 = 0; // Mismatches with pattern starting with '0'
        int diff2 = 0; // Mismatches with pattern starting with '1'
        int minFlips = n;

        // Slide window of length n across virtual concatenated string s + s
        for (int i = 0; i < 2 * n; i++) {
            char curr = s[i % n];
            char target1 = (i % 2 == 0) ? '0' : '1';
            char target2 = (i % 2 == 0) ? '1' : '0';

            if (curr != target1) diff1++;
            if (curr != target2) diff2++;

            if (i >= n) {
                char out = s[(i - n) % n];
                char outTarget1 = ((i - n) % 2 == 0) ? '0' : '1';
                char outTarget2 = ((i - n) % 2 == 0) ? '1' : '0';

                if (out != outTarget1) diff1--;
                if (out != outTarget2) diff2--;
            }

            if (i >= n - 1) {
                minFlips = min({minFlips, diff1, diff2});
            }
        }

        return minFlips;
    }
};

/**
 * Problem: LeetCode 1888 - Minimum Number of Flips to Make the Binary String Alternating
 * Difficulty: Medium
 * Language: JavaScript
 * Author: CodeByTushu
 */
/**
 * @param {string} s
 * @return {number}
 */
var minFlips = function(s) {
    const n = s.length;
    let diff1 = 0; // Mismatches with pattern starting with '0'
    let diff2 = 0; // Mismatches with pattern starting with '1'
    let minFlips = n;

    // Slide window of length n over virtual doubled string
    for (let i = 0; i < 2 * n; i++) {
        const curr = s[i % n];
        const target1 = (i % 2 === 0) ? '0' : '1';
        const target2 = (i % 2 === 0) ? '1' : '0';

        if (curr !== target1) diff1++;
        if (curr !== target2) diff2++;

        if (i >= n) {
            const out = s[(i - n) % n];
            const outTarget1 = ((i - n) % 2 === 0) ? '0' : '1';
            const outTarget2 = ((i - n) % 2 === 0) ? '1' : '0';

            if (out !== outTarget1) diff1--;
            if (out !== outTarget2) diff2--;
        }

        if (i >= n - 1) {
            minFlips = Math.min(minFlips, diff1, diff2);
        }
    }

    return minFlips;
};