1888. Minimum Number of Flips to Make The Binary String Alternating - Explanation

Description

You may perform these operations on the binary string s in any order:

Move its first character to the end. This rotation is free.
Flip any one character, changing 0 to 1 or 1 to 0.

Return the fewest flips needed to make the string alternating, meaning every pair of adjacent characters differs. Only flips are counted; you may perform any number of rotations. The first and last characters do not need to differ.

Example 1:

Input: s = "001"

Output: 0

Explanation: Move the first 0 to the end to obtain 010. This is already alternating, so the rotation needs no flips.

Example 2:

Input: s = "0001"

Output: 1

Explanation: Flip the second character to obtain 0101. No rotation of 0001 is alternating, so one flip is necessary.

Example 3:

Input: s = "0000"

Output: 2

Explanation: Flip the second and fourth characters to obtain 0101. Any alternating string of length four needs two ones, so two flips are necessary.

Constraints:

1 <= s.length <= 100000
Every character is 0 or 1.

Topics

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

Sliding Window Technique - Efficiently processing subarrays/substrings by maintaining a window of fixed or variable size
String Manipulation - Working with rotations and pattern matching in strings
Modular Arithmetic - Using mod operator to simulate circular array traversal
Dynamic Programming - Tracking state transitions as elements shift positions

1. Brute Force

Intuition

An alternating string is either "010101..." or "101010...". The type-1 operation (moving first character to end) lets us try all possible rotations of the string. For each rotation, we count how many flips are needed to match either target pattern.

We generate both alternating patterns of length n, then for each of the n possible rotations, compute the difference count against both patterns and track the minimum.

Algorithm

Build two target patterns: alt1 starting with '0' and alt2 starting with '1'.
For each rotation index i from 0 to n-1:
- Create the rotated string by moving the first i characters to the end.
- Count mismatches with both alt1 and alt2.
- Update the minimum flip count.
Return the minimum found.

class Solution:
    def minFlips(self, s: str) -> int:
        res = n = len(s)
        alt1, alt2 = [], []
        for i in range(n):
            alt1.append("0" if i % 2 == 0 else "1")
            alt2.append("1" if i % 2 == 0 else "0")

        def diff(A, B):
            cnt = 0
            for i in range(n):
                cnt += 1 if (A[i] != B[i]) else 0
            return cnt

        for i in range(n):
            newS = s[i:] + s[:i]
            res = min(res, min(diff(alt1, newS), diff(alt2, newS)))
        return res

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

        for (int i = 0; i < n; i++) {
            alt1.append(i % 2 == 0 ? '0' : '1');
            alt2.append(i % 2 == 0 ? '1' : '0');
        }

        for (int i = 0; i < n; i++) {
            String newS = s.substring(i) + s.substring(0, i);
            res = Math.min(res, Math.min(diff(alt1, newS), diff(alt2, newS)));
        }

        return res;
    }

    private int diff(StringBuilder a, String b) {
        int cnt = 0;
        for (int i = 0; i < a.length(); i++) {
            if (a.charAt(i) != b.charAt(i)) cnt++;
        }
        return cnt;
    }
}

class Solution {
public:
    int minFlips(string s) {
        int n = s.size(), res = n;
        string alt1, alt2;

        for (int i = 0; i < n; i++) {
            alt1 += (i % 2 == 0) ? '0' : '1';
            alt2 += (i % 2 == 0) ? '1' : '0';
        }

        for (int i = 0; i < n; i++) {
            string newS = s.substr(i) + s.substr(0, i);
            res = min(res, min(diff(alt1, newS), diff(alt2, newS)));
        }

        return res;
    }

private:
    int diff(const string &a, const string &b) {
        int cnt = 0;
        for (int i = 0; i < a.size(); i++) {
            if (a[i] != b[i]) cnt++;
        }
        return cnt;
    }
};

class Solution {
    /**
     * @param {string} s
     * @return {number}
     */
    minFlips(s) {
        const n = s.length;
        let res = n;
        let alt1 = '',
            alt2 = '';

        for (let i = 0; i < n; i++) {
            alt1 += i % 2 === 0 ? '0' : '1';
            alt2 += i % 2 === 0 ? '1' : '0';
        }

        const diff = (a, b) => {
            let cnt = 0;
            for (let i = 0; i < a.length; i++) {
                if (a[i] !== b[i]) cnt++;
            }
            return cnt;
        };

        for (let i = 0; i < n; i++) {
            const newS = s.slice(i) + s.slice(0, i);
            res = Math.min(res, Math.min(diff(alt1, newS), diff(alt2, newS)));
        }

        return res;
    }
}

public class Solution {
    public int MinFlips(string s) {
        int n = s.Length, res = n;
        string alt1 = "", alt2 = "";

        for (int i = 0; i < n; i++) {
            alt1 += i % 2 == 0 ? '0' : '1';
            alt2 += i % 2 == 0 ? '1' : '0';
        }

        for (int i = 0; i < n; i++) {
            string newS = s.Substring(i) + s.Substring(0, i);
            res = Math.Min(res, Math.Min(Diff(alt1, newS), Diff(alt2, newS)));
        }

        return res;
    }

    private int Diff(string a, string b) {
        int cnt = 0;
        for (int i = 0; i < a.Length; i++) {
            if (a[i] != b[i]) cnt++;
        }
        return cnt;
    }
}

func minFlips(s string) int {
    n := len(s)
    res := n
    alt1, alt2 := "", ""

    for i := 0; i < n; i++ {
        if i%2 == 0 {
            alt1 += "0"
            alt2 += "1"
        } else {
            alt1 += "1"
            alt2 += "0"
        }
    }

    diff := func(a, b string) int {
        cnt := 0
        for i := 0; i < len(a); i++ {
            if a[i] != b[i] {
                cnt++
            }
        }
        return cnt
    }

    for i := 0; i < n; i++ {
        newS := s[i:] + s[:i]
        res = min(res, min(diff(alt1, newS), diff(alt2, newS)))
    }

    return res
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

class Solution {
    fun minFlips(s: String): Int {
        val n = s.length
        var res = n
        var alt1 = StringBuilder()
        var alt2 = StringBuilder()

        for (i in 0 until n) {
            alt1.append(if (i % 2 == 0) '0' else '1')
            alt2.append(if (i % 2 == 0) '1' else '0')
        }

        fun diff(a: String, b: String): Int {
            var cnt = 0
            for (i in a.indices) {
                if (a[i] != b[i]) cnt++
            }
            return cnt
        }

        for (i in 0 until n) {
            val newS = s.substring(i) + s.substring(0, i)
            res = minOf(res, minOf(diff(alt1.toString(), newS), diff(alt2.toString(), newS)))
        }

        return res
    }
}

class Solution {
    func minFlips(_ s: String) -> Int {
        let n = s.count
        var res = n
        var alt1 = ""
        var alt2 = ""
        let chars = Array(s)

        for i in 0..<n {
            alt1 += i % 2 == 0 ? "0" : "1"
            alt2 += i % 2 == 0 ? "1" : "0"
        }

        func diff(_ a: String, _ b: String) -> Int {
            var cnt = 0
            let aArr = Array(a)
            let bArr = Array(b)
            for i in 0..<aArr.count {
                if aArr[i] != bArr[i] { cnt += 1 }
            }
            return cnt
        }

        for i in 0..<n {
            let newS = String(chars[i...]) + String(chars[..<i])
            res = min(res, min(diff(alt1, newS), diff(alt2, newS)))
        }

        return res
    }
}

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(n)$

2. Brute Force (Space Optimized)

Intuition

Instead of creating explicit rotated strings, we can iterate circularly through the original string using modular arithmetic. For each starting position, we walk through all n characters and count mismatches against both alternating patterns on the fly.

This saves the O(n) space needed to store rotated strings while maintaining the same logic: try every rotation and count flips needed for both target patterns.

Algorithm

For each starting position i:
- Initialize counters for mismatches against "010..." and "101...".
- Walk through n characters using modular indexing (i + k) % n.
- Toggle the expected character as we go.
- Track the minimum between both pattern mismatches.
Return the overall minimum.

class Solution:
    def minFlips(self, s: str) -> int:
        n = res = len(s)

        for i in range(n):
            start_0 = 1 if s[i] != '0' else 0
            start_1 = 1 if s[i] != '1' else 0
            c = '0'
            j = (i + 1) % n
            while j != i:
                start_1 += 1 if s[j] != c else 0
                start_0 += 1 if s[j] == c else 0
                c = '0' if c == '1' else '1'
                j = (j + 1) % n

            res = min(res, min(start_1, start_0))
        return res

public class Solution {
    public int minFlips(String s) {
        int n = s.length();
        int res = n;

        for (int i = 0; i < n; i++) {
            int start0 = s.charAt(i) != '0' ? 1 : 0;
            int start1 = s.charAt(i) != '1' ? 1 : 0;
            char c = '0';
            int j = (i + 1) % n;

            while (j != i) {
                start1 += s.charAt(j) != c ? 1 : 0;
                start0 += s.charAt(j) == c ? 1 : 0;
                c = c == '1' ? '0' : '1';
                j = (j + 1) % n;
            }

            res = Math.min(res, Math.min(start1, start0));
        }

        return res;
    }
}

class Solution {
public:
    int minFlips(string s) {
        int n = s.size(), res = n;

        for (int i = 0; i < n; i++) {
            int start0 = (s[i] != '0') ? 1 : 0;
            int start1 = (s[i] != '1') ? 1 : 0;
            char c = '0';
            int j = (i + 1) % n;

            while (j != i) {
                start1 += (s[j] != c) ? 1 : 0;
                start0 += (s[j] == c) ? 1 : 0;
                c = (c == '1') ? '0' : '1';
                j = (j + 1) % n;
            }

            res = min(res, min(start1, start0));
        }

        return res;
    }
};

class Solution {
    /**
     * @param {string} s
     * @return {number}
     */
    minFlips(s) {
        const n = s.length;
        let res = n;

        for (let i = 0; i < n; i++) {
            let start0 = s[i] !== '0' ? 1 : 0;
            let start1 = s[i] !== '1' ? 1 : 0;
            let c = '0';
            let j = (i + 1) % n;

            while (j !== i) {
                start1 += s[j] !== c ? 1 : 0;
                start0 += s[j] === c ? 1 : 0;
                c = c === '1' ? '0' : '1';
                j = (j + 1) % n;
            }

            res = Math.min(res, Math.min(start1, start0));
        }

        return res;
    }
}

public class Solution {
    public int MinFlips(string s) {
        int n = s.Length;
        int res = n;

        for (int i = 0; i < n; i++) {
            int start0 = s[i] != '0' ? 1 : 0;
            int start1 = s[i] != '1' ? 1 : 0;
            char c = '0';
            int j = (i + 1) % n;

            while (j != i) {
                start1 += s[j] != c ? 1 : 0;
                start0 += s[j] == c ? 1 : 0;
                c = c == '1' ? '0' : '1';
                j = (j + 1) % n;
            }

            res = Math.Min(res, Math.Min(start1, start0));
        }

        return res;
    }
}

func minFlips(s string) int {
    n := len(s)
    res := n

    for i := 0; i < n; i++ {
        start0, start1 := 0, 0
        if s[i] != '0' {
            start0 = 1
        }
        if s[i] != '1' {
            start1 = 1
        }
        c := byte('0')
        j := (i + 1) % n

        for j != i {
            if s[j] != c {
                start1++
            }
            if s[j] == c {
                start0++
            }
            if c == '1' {
                c = '0'
            } else {
                c = '1'
            }
            j = (j + 1) % n
        }

        res = min(res, min(start1, start0))
    }

    return res
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

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

        for (i in 0 until n) {
            var start0 = if (s[i] != '0') 1 else 0
            var start1 = if (s[i] != '1') 1 else 0
            var c = '0'
            var j = (i + 1) % n

            while (j != i) {
                start1 += if (s[j] != c) 1 else 0
                start0 += if (s[j] == c) 1 else 0
                c = if (c == '1') '0' else '1'
                j = (j + 1) % n
            }

            res = minOf(res, minOf(start1, start0))
        }

        return res
    }
}

class Solution {
    func minFlips(_ s: String) -> Int {
        let n = s.count
        var res = n
        let chars = Array(s)

        for i in 0..<n {
            var start0 = chars[i] != Character("0") ? 1 : 0
            var start1 = chars[i] != Character("1") ? 1 : 0
            var c: Character = "0"
            var j = (i + 1) % n

            while j != i {
                start1 += chars[j] != c ? 1 : 0
                start0 += chars[j] == c ? 1 : 0
                c = c == "1" ? "0" : "1"
                j = (j + 1) % n
            }

            res = min(res, min(start1, start0))
        }

        return res
    }
}

impl Solution {
    pub fn min_flips(s: String) -> i32 {
        let s = s.as_bytes();
        let n = s.len();
        let mut res = n as i32;

        for i in 0..n {
            let mut start0 = if s[i] != b'0' { 1 } else { 0 };
            let mut start1 = if s[i] != b'1' { 1 } else { 0 };
            let mut c = b'0';
            let mut j = (i + 1) % n;

            while j != i {
                if s[j] != c { start1 += 1; }
                if s[j] == c { start0 += 1; }
                c = if c == b'1' { b'0' } else { b'1' };
                j = (j + 1) % n;
            }

            res = res.min(start1.min(start0));
        }

        res
    }
}

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(1)$ extra space.

3. Sliding Window

Intuition

Concatenating the string with itself (s + s) simulates all rotations. A window of size n sliding over this doubled string represents each rotation. We can maintain mismatch counts incrementally: add the new character's contribution when expanding the window, and remove the old character's contribution when shrinking.

This transforms the O(n^2) brute force into O(n) by avoiding recalculation of the full difference for each rotation.

Algorithm

Double the string: s = s + s.
Build alternating patterns of length 2n.
Use two pointers l and r to maintain a window of size n:
- As r expands, update diff1 and diff2 based on mismatches at position r.
- When window exceeds size n, remove contribution from position l and advance l.
- When window is exactly size n, record the minimum of diff1 and diff2.
Return the minimum.

class Solution:
    def minFlips(self, s: str) -> int:
        n = len(s)
        s = s + s
        alt1, alt2 = [], []
        for i in range(len(s)):
            alt1.append("0" if i % 2 == 0 else "1")
            alt2.append("1" if i % 2 == 0 else "0")

        res = len(s)
        diff1, diff2 = 0, 0
        l = 0

        for r in range(len(s)):
            if s[r] != alt1[r]:
                diff1 += 1
            if s[r] != alt2[r]:
                diff2 += 1

            if r - l + 1 > n:
                if s[l] != alt1[l]:
                    diff1 -= 1
                if s[l] != alt2[l]:
                    diff2 -= 1
                l += 1

            if r - l + 1 == n:
                res = min(res, diff1, diff2)

        return res

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

        for (int i = 0; i < s.length(); i++) {
            alt1.append(i % 2 == 0 ? '0' : '1');
            alt2.append(i % 2 == 0 ? '1' : '0');
        }

        int res = n, diff1 = 0, diff2 = 0, l = 0;

        for (int r = 0; r < s.length(); r++) {
            if (s.charAt(r) != alt1.charAt(r)) diff1++;
            if (s.charAt(r) != alt2.charAt(r)) diff2++;

            if (r - l + 1 > n) {
                if (s.charAt(l) != alt1.charAt(l)) diff1--;
                if (s.charAt(l) != alt2.charAt(l)) diff2--;
                l++;
            }

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

        return res;
    }
}

class Solution {
public:
    int minFlips(string s) {
        int n = s.size();
        s += s;
        string alt1, alt2;
        for (int i = 0; i < s.size(); i++) {
            alt1 += (i % 2 == 0) ? '0' : '1';
            alt2 += (i % 2 == 0) ? '1' : '0';
        }

        int res = n, diff1 = 0, diff2 = 0, l = 0;

        for (int r = 0; r < s.size(); r++) {
            if (s[r] != alt1[r]) diff1++;
            if (s[r] != alt2[r]) diff2++;

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

            if (r - l + 1 == n) {
                res = min(res, min(diff1, diff2));
            }
        }

        return res;
    }
};

class Solution {
    /**
     * @param {string} s
     * @return {number}
     */
    minFlips(s) {
        const n = s.length;
        s = s + s;
        let alt1 = [],
            alt2 = [];

        for (let i = 0; i < s.length; i++) {
            alt1.push(i % 2 === 0 ? '0' : '1');
            alt2.push(i % 2 === 0 ? '1' : '0');
        }

        let res = n,
            diff1 = 0,
            diff2 = 0,
            l = 0;

        for (let r = 0; r < s.length; r++) {
            if (s[r] !== alt1[r]) diff1++;
            if (s[r] !== alt2[r]) diff2++;

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

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

        return res;
    }
}

public class Solution {
    public int MinFlips(string s) {
        int n = s.Length;
        s = s + s;
        var alt1 = new char[s.Length];
        var alt2 = new char[s.Length];

        for (int i = 0; i < s.Length; i++) {
            alt1[i] = i % 2 == 0 ? '0' : '1';
            alt2[i] = i % 2 == 0 ? '1' : '0';
        }

        int res = n, diff1 = 0, diff2 = 0, l = 0;

        for (int r = 0; r < s.Length; r++) {
            if (s[r] != alt1[r]) diff1++;
            if (s[r] != alt2[r]) diff2++;

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

            if (r - l + 1 == n) {
                res = Math.Min(res, Math.Min(diff1, diff2));
            }
        }

        return res;
    }
}

class Solution {
    fun minFlips(s: String): Int {
        val n = s.length
        val doubled = s + s
        val alt1 = CharArray(doubled.length)
        val alt2 = CharArray(doubled.length)

        for (i in doubled.indices) {
            alt1[i] = if (i % 2 == 0) '0' else '1'
            alt2[i] = if (i % 2 == 0) '1' else '0'
        }

        var res = n
        var diff1 = 0
        var diff2 = 0
        var l = 0

        for (r in doubled.indices) {
            if (doubled[r] != alt1[r]) diff1++
            if (doubled[r] != alt2[r]) diff2++

            if (r - l + 1 > n) {
                if (doubled[l] != alt1[l]) diff1--
                if (doubled[l] != alt2[l]) diff2--
                l++
            }

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

        return res
    }
}

class Solution {
    func minFlips(_ s: String) -> Int {
        let n = s.count
        let doubled = s + s
        let chars = Array(doubled)
        var alt1 = [Character](repeating: "0", count: chars.count)
        var alt2 = [Character](repeating: "0", count: chars.count)

        for i in 0..<chars.count {
            alt1[i] = i % 2 == 0 ? "0" : "1"
            alt2[i] = i % 2 == 0 ? "1" : "0"
        }

        var res = n, diff1 = 0, diff2 = 0, l = 0

        for r in 0..<chars.count {
            if chars[r] != alt1[r] { diff1 += 1 }
            if chars[r] != alt2[r] { diff2 += 1 }

            if r - l + 1 > n {
                if chars[l] != alt1[l] { diff1 -= 1 }
                if chars[l] != alt2[l] { diff2 -= 1 }
                l += 1
            }

            if r - l + 1 == n {
                res = min(res, min(diff1, diff2))
            }
        }

        return res
    }
}

impl Solution {
    pub fn min_flips(s: String) -> i32 {
        let n = s.len();
        let s = s.as_bytes();
        let doubled: Vec<u8> = s.iter().chain(s.iter()).copied().collect();
        let alt1: Vec<u8> = (0..doubled.len()).map(|i| if i % 2 == 0 { b'0' } else { b'1' }).collect();
        let alt2: Vec<u8> = (0..doubled.len()).map(|i| if i % 2 == 0 { b'1' } else { b'0' }).collect();

        let mut res = n as i32;
        let (mut diff1, mut diff2, mut l) = (0i32, 0i32, 0usize);

        for r in 0..doubled.len() {
            if doubled[r] != alt1[r] { diff1 += 1; }
            if doubled[r] != alt2[r] { diff2 += 1; }

            if r - l + 1 > n {
                if doubled[l] != alt1[l] { diff1 -= 1; }
                if doubled[l] != alt2[l] { diff2 -= 1; }
                l += 1;
            }

            if r - l + 1 == n {
                res = res.min(diff1.min(diff2));
            }
        }

        res
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

4. Sliding Window (Space Optimized)

Intuition

We can avoid storing the doubled string and alternating patterns by computing expected characters on the fly. By tracking what character position r should have (toggling between '0' and '1'), we update mismatch counts directly.

Using modular indexing s[r % n] simulates the doubled string. We track the expected starting character for both window boundaries and toggle as we slide.

Algorithm

Initialize difference counters and window boundaries.
For r from 0 to 2n - 1:
- Compute expected character at position r for pattern starting with '0'.
- Update both mismatch counts based on whether s[r % n] matches.
- If window exceeds size n, remove contribution from s[l] and advance l.
- When window equals size n, update minimum.
Toggle expected characters as window slides.

class Solution:
    def minFlips(self, s: str) -> int:
        res = n = len(s)
        diff1 = diff2 = l = 0

        rstart_0 = lstart_0 = '0'

        for r in range(2 * n):
            if s[r % n] != rstart_0:
                diff1 += 1
            if s[r % n] == rstart_0:
                diff2 += 1

            if r - l + 1 > n:
                if s[l] != lstart_0:
                    diff1 -= 1
                if s[l] == lstart_0:
                    diff2 -= 1
                l += 1
                lstart_0 = '1' if lstart_0 == '0' else '0'

            if r - l + 1 == n:
                res = min(res, diff1, diff2)

            rstart_0 = '1' if rstart_0 == '0' else '0'

        return res

public class Solution {
    public int minFlips(String s) {
        int n = s.length();
        int res = n, diff1 = 0, diff2 = 0, l = 0;

        char rstart_0 = '0', lstart_0 = '0';

        for (int r = 0; r < 2 * n; r++) {
            if (s.charAt(r % n) != rstart_0) diff1++;
            if (s.charAt(r % n) == rstart_0) diff2++;

            if (r - l + 1 > n) {
                if (s.charAt(l) != lstart_0) diff1--;
                if (s.charAt(l) == lstart_0) diff2--;
                l++;
                lstart_0 = (lstart_0 == '0') ? '1' : '0';
            }

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

            rstart_0 = (rstart_0 == '0') ? '1' : '0';
        }

        return res;
    }
}

class Solution {
public:
    int minFlips(string s) {
        int n = s.size();
        int res = n, diff1 = 0, diff2 = 0, l = 0;

        char rstart_0 = '0', lstart_0 = '0';

        for (int r = 0; r < 2 * n; r++) {
            if (s[r % n] != rstart_0) diff1++;
            if (s[r % n] == rstart_0) diff2++;

            if (r - l + 1 > n) {
                if (s[l] != lstart_0) diff1--;
                if (s[l] == lstart_0) diff2--;
                l++;
                lstart_0 = (lstart_0 == '0') ? '1' : '0';
            }

            if (r - l + 1 == n) {
                res = min(res, min(diff1, diff2));
            }

            rstart_0 = (rstart_0 == '0') ? '1' : '0';
        }

        return res;
    }
};

class Solution {
    /**
     * @param {string} s
     * @return {number}
     */
    minFlips(s) {
        const n = s.length;
        let res = n,
            diff1 = 0,
            diff2 = 0,
            l = 0;

        let rstart_0 = '0',
            lstart_0 = '0';

        for (let r = 0; r < 2 * n; r++) {
            if (s[r % n] !== rstart_0) diff1++;
            if (s[r % n] === rstart_0) diff2++;

            if (r - l + 1 > n) {
                if (s[l] !== lstart_0) diff1--;
                if (s[l] === lstart_0) diff2--;
                l++;
                lstart_0 = lstart_0 === '0' ? '1' : '0';
            }

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

            rstart_0 = rstart_0 === '0' ? '1' : '0';
        }

        return res;
    }
}

public class Solution {
    public int MinFlips(string s) {
        int n = s.Length;
        int res = n, diff1 = 0, diff2 = 0, l = 0;

        char rstart_0 = '0', lstart_0 = '0';

        for (int r = 0; r < 2 * n; r++) {
            if (s[r % n] != rstart_0) diff1++;
            if (s[r % n] == rstart_0) diff2++;

            if (r - l + 1 > n) {
                if (s[l] != lstart_0) diff1--;
                if (s[l] == lstart_0) diff2--;
                l++;
                lstart_0 = lstart_0 == '0' ? '1' : '0';
            }

            if (r - l + 1 == n) {
                res = Math.Min(res, Math.Min(diff1, diff2));
            }

            rstart_0 = rstart_0 == '0' ? '1' : '0';
        }

        return res;
    }
}

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

        var rstart_0 = '0'
        var lstart_0 = '0'

        for (r in 0 until 2 * n) {
            if (s[r % n] != rstart_0) diff1++
            if (s[r % n] == rstart_0) diff2++

            if (r - l + 1 > n) {
                if (s[l] != lstart_0) diff1--
                if (s[l] == lstart_0) diff2--
                l++
                lstart_0 = if (lstart_0 == '0') '1' else '0'
            }

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

            rstart_0 = if (rstart_0 == '0') '1' else '0'
        }

        return res
    }
}

class Solution {
    func minFlips(_ s: String) -> Int {
        let n = s.count
        var res = n, diff1 = 0, diff2 = 0, l = 0
        let chars = Array(s)

        var rstart_0: Character = "0"
        var lstart_0: Character = "0"

        for r in 0..<(2 * n) {
            if chars[r % n] != rstart_0 { diff1 += 1 }
            if chars[r % n] == rstart_0 { diff2 += 1 }

            if r - l + 1 > n {
                if chars[l] != lstart_0 { diff1 -= 1 }
                if chars[l] == lstart_0 { diff2 -= 1 }
                l += 1
                lstart_0 = lstart_0 == "0" ? "1" : "0"
            }

            if r - l + 1 == n {
                res = min(res, min(diff1, diff2))
            }

            rstart_0 = rstart_0 == "0" ? "1" : "0"
        }

        return res
    }
}

impl Solution {
    pub fn min_flips(s: String) -> i32 {
        let s = s.as_bytes();
        let n = s.len();
        let mut res = n as i32;
        let (mut diff1, mut diff2, mut l) = (0i32, 0i32, 0usize);
        let mut rstart_0 = b'0';
        let mut lstart_0 = b'0';

        for r in 0..2 * n {
            if s[r % n] != rstart_0 { diff1 += 1; }
            if s[r % n] == rstart_0 { diff2 += 1; }

            if r - l + 1 > n {
                if s[l] != lstart_0 { diff1 -= 1; }
                if s[l] == lstart_0 { diff2 -= 1; }
                l += 1;
                lstart_0 = if lstart_0 == b'0' { b'1' } else { b'0' };
            }

            if r - l + 1 == n {
                res = res.min(diff1.min(diff2));
            }

            rstart_0 = if rstart_0 == b'0' { b'1' } else { b'0' };
        }

        res
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$ extra space.

5. Dynamic Programming

Intuition

First, count mismatches for the original string against pattern "1010...". The mismatch count for "0101..." is simply n - start_1 since every position either matches one pattern or the other.

For odd-length strings, rotating changes parity. After one rotation, positions that needed a '0' now need a '1' and vice versa. We can compute the new mismatch counts by swapping and adjusting based on the character that moved from front to back.

Algorithm

Count initial mismatches (start_1) against pattern "101...".
Compute start_0 = n - start_1 for pattern "010...".
If n is even, rotations do not change the answer, so return min(start_0, start_1).
For odd n, simulate each rotation:
- Swap dp0 and dp1 (parity flip).
- Adjust counts based on the character that rotated.
- Track minimum across all rotations.

class Solution:
    def minFlips(self, s: str) -> int:
        start_1 = 0
        for i in range(len(s)):
            if i & 1:
                start_1 += s[i] == "1"
            else:
                start_1 += s[i] == "0"

        start_0 = len(s) - start_1
        ans = min(start_0, start_1)
        if len(s) % 2 == 0:
            return ans

        dp0, dp1 = start_0, start_1
        for c in s:
            dp0, dp1 = dp1, dp0
            if c == "1":
                dp0 += 1
                dp1 -= 1
            else:
                dp0 -= 1
                dp1 += 1
            ans = min(dp0, dp1, ans)
        return ans

public class Solution {
    public int minFlips(String s) {
        int start_1 = 0;
        int n = s.length();

        for (int i = 0; i < n; i++) {
            if ((i & 1) == 1) {
                start_1 += s.charAt(i) == '1' ? 1 : 0;
            } else {
                start_1 += s.charAt(i) == '0' ? 1 : 0;
            }
        }

        int start_0 = n - start_1;
        int ans = Math.min(start_0, start_1);
        if (n % 2 == 0) {
            return ans;
        }

        int dp0 = start_0, dp1 = start_1;
        for (char c : s.toCharArray()) {
            int temp = dp0;
            dp0 = dp1;
            dp1 = temp;
            if (c == '1') {
                dp0++;
                dp1--;
            } else {
                dp0--;
                dp1++;
            }
            ans = Math.min(ans, Math.min(dp0, dp1));
        }

        return ans;
    }
}

class Solution {
public:
    int minFlips(string s) {
        int start_1 = 0, n = s.size();

        for (int i = 0; i < n; i++) {
            if (i & 1) {
                start_1 += (s[i] == '1');
            } else {
                start_1 += (s[i] == '0');
            }
        }

        int start_0 = n - start_1;
        int ans = min(start_0, start_1);
        if (n % 2 == 0) {
            return ans;
        }

        int dp0 = start_0, dp1 = start_1;
        for (char c : s) {
            int temp = dp0;
            dp0 = dp1;
            dp1 = temp;
            if (c == '1') {
                dp0++;
                dp1--;
            } else {
                dp0--;
                dp1++;
            }
            ans = min({ans, dp0, dp1});
        }

        return ans;
    }
};

class Solution {
    /**
     * @param {string} s
     * @return {number}
     */
    minFlips(s) {
        let start_1 = 0;
        const n = s.length;

        for (let i = 0; i < n; i++) {
            if (i & 1) {
                start_1 += s[i] === '1' ? 1 : 0;
            } else {
                start_1 += s[i] === '0' ? 1 : 0;
            }
        }

        let start_0 = n - start_1;
        let ans = Math.min(start_0, start_1);
        if (n % 2 === 0) {
            return ans;
        }

        let dp0 = start_0,
            dp1 = start_1;
        for (const c of s) {
            [dp0, dp1] = [dp1, dp0];
            if (c === '1') {
                dp0++;
                dp1--;
            } else {
                dp0--;
                dp1++;
            }
            ans = Math.min(ans, dp0, dp1);
        }

        return ans;
    }
}

public class Solution {
    public int MinFlips(string s) {
        int start_1 = 0;
        int n = s.Length;

        for (int i = 0; i < n; i++) {
            if ((i & 1) == 1) {
                start_1 += s[i] == '1' ? 1 : 0;
            } else {
                start_1 += s[i] == '0' ? 1 : 0;
            }
        }

        int start_0 = n - start_1;
        int ans = Math.Min(start_0, start_1);
        if (n % 2 == 0) {
            return ans;
        }

        int dp0 = start_0, dp1 = start_1;
        foreach (char c in s) {
            int temp = dp0;
            dp0 = dp1;
            dp1 = temp;
            if (c == '1') {
                dp0++;
                dp1--;
            } else {
                dp0--;
                dp1++;
            }
            ans = Math.Min(ans, Math.Min(dp0, dp1));
        }

        return ans;
    }
}

func minFlips(s string) int {
    start_1 := 0
    n := len(s)

    for i := 0; i < n; i++ {
        if i&1 == 1 {
            if s[i] == '1' {
                start_1++
            }
        } else {
            if s[i] == '0' {
                start_1++
            }
        }
    }

    start_0 := n - start_1
    ans := min(start_0, start_1)
    if n%2 == 0 {
        return ans
    }

    dp0, dp1 := start_0, start_1
    for i := 0; i < n; i++ {
        dp0, dp1 = dp1, dp0
        if s[i] == '1' {
            dp0++
            dp1--
        } else {
            dp0--
            dp1++
        }
        ans = min(ans, min(dp0, dp1))
    }

    return ans
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

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

        for (i in 0 until n) {
            if (i and 1 == 1) {
                start_1 += if (s[i] == '1') 1 else 0
            } else {
                start_1 += if (s[i] == '0') 1 else 0
            }
        }

        var start_0 = n - start_1
        var ans = minOf(start_0, start_1)
        if (n % 2 == 0) {
            return ans
        }

        var dp0 = start_0
        var dp1 = start_1
        for (c in s) {
            val temp = dp0
            dp0 = dp1
            dp1 = temp
            if (c == '1') {
                dp0++
                dp1--
            } else {
                dp0--
                dp1++
            }
            ans = minOf(ans, minOf(dp0, dp1))
        }

        return ans
    }
}

class Solution {
    func minFlips(_ s: String) -> Int {
        var start_1 = 0
        let n = s.count
        let chars = Array(s)

        for i in 0..<n {
            if i & 1 == 1 {
                start_1 += chars[i] == "1" ? 1 : 0
            } else {
                start_1 += chars[i] == "0" ? 1 : 0
            }
        }

        var start_0 = n - start_1
        var ans = min(start_0, start_1)
        if n % 2 == 0 {
            return ans
        }

        var dp0 = start_0, dp1 = start_1
        for c in chars {
            let temp = dp0
            dp0 = dp1
            dp1 = temp
            if c == "1" {
                dp0 += 1
                dp1 -= 1
            } else {
                dp0 -= 1
                dp1 += 1
            }
            ans = min(ans, min(dp0, dp1))
        }

        return ans
    }
}

impl Solution {
    pub fn min_flips(s: String) -> i32 {
        let s = s.as_bytes();
        let n = s.len() as i32;

        let mut start_1 = 0i32;
        for i in 0..n as usize {
            if i & 1 == 1 {
                start_1 += if s[i] == b'1' { 1 } else { 0 };
            } else {
                start_1 += if s[i] == b'0' { 1 } else { 0 };
            }
        }

        let start_0 = n - start_1;
        let mut ans = start_0.min(start_1);
        if n % 2 == 0 {
            return ans;
        }

        let (mut dp0, mut dp1) = (start_0, start_1);
        for &c in s.iter() {
            std::mem::swap(&mut dp0, &mut dp1);
            if c == b'1' {
                dp0 += 1;
                dp1 -= 1;
            } else {
                dp0 -= 1;
                dp1 += 1;
            }
            ans = ans.min(dp0.min(dp1));
        }

        ans
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$ extra space.

Common Pitfalls

Forgetting That Rotations Only Matter for Odd-Length Strings

For even-length strings, rotating the string does not change the number of flips needed because the parity of each position remains the same after a full rotation cycle. The optimization to skip rotations when n % 2 == 0 is critical for both correctness and performance. Without this check, you might perform unnecessary work or miss that the initial comparison already gives the optimal answer.

Incorrectly Handling the Doubled String in Sliding Window

When using the sliding window approach with s + s, you must build alternating patterns of length 2n, not n. If you only build patterns of length n and try to index beyond, you will get index-out-of-bounds errors or incorrect mismatch counts. Additionally, when the window slides, you must properly remove the contribution of the leftmost character before adding the new rightmost character.

Confusing Which Pattern Tracks Which Mismatches

The two patterns "010101..." and "101010..." are complementary. If a position matches one pattern, it mismatches the other. When computing both diff counts simultaneously, ensure you are consistent: if s[r] != alt1[r], increment diff1; if s[r] != alt2[r], increment diff2. Mixing up which count corresponds to which pattern will produce incorrect minimum flip counts.