LeetCode Entry

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

07.03.2026 medium 2026 kotlin rust

Min flips to make 01 alterating string sum window

1888. Minimum Number of Flips to Make the Binary String Alternating medium blog post substack youtube

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/1290

Problem TLDR

Min flips to make 01 alterating string #medium #prefix_sum #sliding_window

Intuition

    // 111000
    //  0  1
    //
    // 110001
    // 100011
    //   1
    //      0
    //
    // whats the point of shifting?
    //
    // 110
    // 101 just shifted
    //
    // soo we can start from first 10
    //
    // 011
    // 110
    // 101
    //
    // 11010
    //
    // 10110
    // 01011
    //
    // or double 00
    // 001 shift 010
    //
    // just split 11 idk if it works
    //
    // can be many splits
    // is this dp?
    // 0011
    //
    // 101|101
    //
    // not optimal
    // 10001100101000000|10001100101000000
    //  1010101010101010|1
    //   101010101010101|01
    //    10101010101010|101
    //     1010101010101|0101
    // ...
    //                10|101010101010101
    //                 1|0101010101010101
    // they are all repeating
    //
    // 011|011
    // 010|
    //  01|0
    //   0|10
    // 101|
    //  10|1
    //   1|01 match
    // a  | b
    // miss before + (len-miss) after

Prefix sum intuition:

• split at every every index, count bitflips in prefix+suffix(inverted)
• if string length is even return early

Sliding window intuition:

• slide concatenation
• if string length is even slide once
• to move the left pointer flip the bit

Approach

• (c+i)%2 gives a match increment

Complexity

• Time complexity: \(O(n)\)

• Space complexity: \(O(1)\), or O(n) for prefix sum

Code

// 36ms
    fun minFlips(s: String): Int {
        var c = 0
        return (0..<s.length+s.length%2*s.length).minOf { i ->
            c += (s[i%s.length]-'0' + i)%2
            if (i > s.lastIndex) c -= 1-(s[i-s.length]-'0'+i)%2
            if (i < s.lastIndex) s.length else min(c, s.length-c)
        }
    }

// 2ms
    pub fn min_flips(s: String) -> i32 {
        let (n, mut a) = (s.len(), vec![0; s.len()+1]);
        for (i,b) in s.bytes().enumerate() {
            a[i+1]=a[i]+((b+i as u8)&1)as usize }
        if n%2==0 { return a[n].min(n-a[n]) as _ }
        (0..=n).map(|i| {
            let t = a[n] + i - 2 * a[i]; t.min(n - t)
        }).min().unwrap_or(0) as _
    }