LeetCode 1888 – Minimum Number of Flips to Make the Binary String Alternating

In this article, we will clearly understand LeetCode 1888. This is a very interesting Sliding Window + String Rotation problem that often appears in coding interviews.

We will cover:

• Simple problem explanation
• Examples
• Key intuition
• Sliding window technique
• Java implementation
• Other possible approaches
• Time and space complexity

---

Problem Statement

You are given a binary string s consisting of only 0 and 1.

You can perform two operations:

• Rotate the string (move the first character to the end)
• Flip any character (0 → 1 or 1 → 0)

Your goal is to find the minimum number of flips required to make the string alternating.

Alternating strings look like:

010101...
101010...

---

Example

Input:
s = 111000

Possible alternating patterns:

Pattern A: 010101
Pattern B: 101010

Comparison with Pattern B:

s        : 1 1 1 0 0 0
patternB : 1 0 1 0 1 0
             X     X

Minimum flips = 2

---

Important Observation

We are allowed to rotate the string.

Example rotations:

111000
110001
100011
000111

Each rotation may require a different number of flips. Checking every rotation individually would take:

O(n²)

So we need a more efficient approach.

---

Key Trick – Double the String

Instead of performing actual rotations, we duplicate the string.

s = 111000

s + s

111000111000

Now every rotation becomes a substring. Example windows:

111000111000
[111000]

111000111000
 [110001]

111000111000
  [100011]

This allows us to simulate rotations using a sliding window.

---

Create Alternating Target Strings

Pattern1
010101010101

Pattern2
101010101010

Each window will be compared with these patterns.

---

Sliding Window

111000111000
[L-----R]

Move window:

111000111000
 [L-----R]

111000111000
  [L-----R]

For each window we count mismatches.

---

Algorithm Steps

1. Double the string → s + s
2. Create alternating patterns
3. Use sliding window of size n
4. Track mismatches with both patterns
5. Take the minimum flips

---

Java Solution

class Solution {

    public int minFlips(String s) {

        int n = s.length();
        String doubled = s + s;

        int diff1 = 0;
        int diff2 = 0;

        int result = Integer.MAX_VALUE;

        for(int i = 0; i < doubled.length(); i++) {

            char expected1 = (i % 2 == 0) ? '0' : '1';
            char expected2 = (i % 2 == 0) ? '1' : '0';

            if(doubled.charAt(i) != expected1)
                diff1++;

            if(doubled.charAt(i) != expected2)
                diff2++;

            if(i >= n) {

                char prev = doubled.charAt(i - n);

                char prevExpected1 = ((i - n) % 2 == 0) ? '0' : '1';
                char prevExpected2 = ((i - n) % 2 == 0) ? '1' : '0';

                if(prev != prevExpected1)
                    diff1--;

                if(prev != prevExpected2)
                    diff2--;
            }

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

        return result;
    }
}

---

Time and Space Complexity

Time Complexity:  O(n)

Space Complexity: O(n)

---

Other Approaches

Brute Force Rotation

Rotate the string and calculate flips for each rotation.

Time Complexity: O(n²)

Pros

• Easy to implement

Cons

• Too slow for large inputs

---

Precomputed Alternating Strings

Generate alternating patterns and compare each rotation.

Time Complexity: O(n²)

---

Key Takeaway

The important trick in this problem is converting the rotation problem into a sliding window problem.

Once the string is doubled, every rotation appears as a window, allowing us to solve the problem efficiently in O(n) time.

---

Conclusion

LeetCode 1888 is an excellent problem to practice sliding window techniques and string manipulation.

Understanding this trick will help you solve many advanced string problems in coding interviews.

---

Author: ExpertFunda