Minimum Number of Flips to Make the Binary String Alternating

Med

#1724Time: O(N^2), where N is the length of the string. The outer loop runs N times for each rotation. The inner loop also runs N times to calculate the flips for the current rotation.Space: O(N), where N is the length of the string. This space is used to store the mutable copy of the string (e.g., in a `StringBuilder`).1 company

Patterns

Sliding Window Dynamic Programming

Data structures

String

Companies

IBM

Prompt

You are given a binary string s. You are allowed to perform two types of operations on the string in any sequence:

Type-1: Remove the character at the start of the string s and append it to the end of the string.
Type-2: Pick any character in s and flip its value, i.e., if its value is '0' it becomes '1' and vice-versa.

Return the minimum number of type-2 operations you need to perform such that s becomes alternating.

The string is called alternating if no two adjacent characters are equal.

For example, the strings "010" and "1010" are alternating, while the string "0100" is not.

Example 1:

Input: s = "111000"
Output: 2
Explanation: Use the first operation two times to make s = "100011".
Then, use the second operation on the third and sixth elements to make s = "101010".

Example 2:

Input: s = "010"
Output: 0
Explanation: The string is already alternating.

Example 3:

Input: s = "1110"
Output: 1
Explanation: Use the second operation on the second element to make s = "1010".

Constraints:

1 <= s.length <= 10⁵
s[i] is either '0' or '1'.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach directly simulates the problem statement. Since Type-1 operations (rotations) are free, we can try every possible rotation of the string s. For each of these n rotations, we calculate the minimum number of Type-2 operations (flips) needed to make it alternating. The final answer is the minimum value found across all rotations.

For any given string, there are two possible alternating patterns it can be converted to: one starting with '0' (e.g., "01010") and one starting with '1' (e.g., "10101"). We calculate the number of flips needed to achieve both patterns and take the smaller of the two. This process is repeated for all n rotations of the original string.

Algorithm

Initialize min_flips to a very large value.
Let n be the length of the input string s.
Create a mutable version of the string, for example, using StringBuilder.
Loop n times, from i = 0 to n-1, to simulate each of the n possible rotations.
- In each iteration i, we have a new rotated string.
- Calculate the number of flips required to make this rotated string alternating. This requires two calculations:
  1. flips1: Flips to match the pattern "0101...".
  2. flips2: Flips to match the pattern "1010...".
- To calculate flips1 and flips2, iterate from j = 0 to n-1 and compare the character at each position j with the expected characters of the two target patterns.
- Update min_flips with the minimum of its current value, flips1, and flips2.
- Perform one rotation on the string builder (move the first character to the end) to prepare for the next iteration.
After the loop finishes, min_flips will hold the minimum number of flips required for any rotation.

Walkthrough

The algorithm iterates through all n possible cyclic shifts of the string s. In each iteration, it takes the current rotated string and computes the cost to transform it into an alternating string. The cost is the minimum of two values: the number of flips to match the "0101..." pattern and the number of flips to match the "1010..." pattern. The overall minimum cost found among all rotations is the result.

1class Solution {2    public int minFlips(String s) {3        int n = s.length();4        int minFlips = Integer.MAX_VALUE;5        StringBuilder sb = new StringBuilder(s);6 7        // Iterate through all n possible rotations8        for (int i = 0; i < n; i++) {9            // This is the i-th rotated string10            String current_s = sb.toString();11            12            // Calculate flips for the two possible alternating patterns13            int flipsToPattern01 = 0; // for "0101..."14            int flipsToPattern10 = 0; // for "1010..."15            16            for (int j = 0; j < n; j++) {17                // Target pattern starting with '0'18                if (current_s.charAt(j) != (j % 2 == 0 ? '0' : '1')) {19                    flipsToPattern01++;20                }21                // Target pattern starting with '1'22                if (current_s.charAt(j) != (j % 2 == 0 ? '1' : '0')) {23                    flipsToPattern10++;24                }25            }26            27            minFlips = Math.min(minFlips, Math.min(flipsToPattern01, flipsToPattern10));28            29            // Perform one rotation for the next iteration30            char firstChar = sb.charAt(0);31            sb.deleteCharAt(0);32            sb.append(firstChar);33        }34        35        return minFlips;36    }37}

Complexity

Time

O(N^2), where N is the length of the string. The outer loop runs N times for each rotation. The inner loop also runs N times to calculate the flips for the current rotation.

Space

O(N), where N is the length of the string. This space is used to store the mutable copy of the string (e.g., in a `StringBuilder`).

Trade-offs

Pros

It is a straightforward implementation of the problem's logic.
Easy to understand and reason about.

Cons

The time complexity of O(N^2) is too slow for the given constraints (N up to 10^5), leading to a 'Time Limit Exceeded' error on larger inputs.
It performs a lot of redundant calculations. The flip count for each rotation is calculated from scratch, while adjacent rotations share N-1 characters.

A more efficient approach uses a sliding window technique to avoid re-calculating flips for each rotation. The key idea is that any rotation of s is a contiguous substring of length n in the string s + s. By creating this doubled string, we can find the minimum flips for all rotations by sliding a window of size n across it.

We can pre-calculate the mismatches for the entire doubled string against two fixed alternating patterns ("0101..." and "1010..."). Then, as we slide our window, we can update the total mismatches for the window in constant time by subtracting the contribution of the character that leaves the window and adding the contribution of the character that enters. This reduces the overall time complexity from quadratic to linear.

Algorithm

Let n be the length of s.
Create a new string s_double by concatenating s with itself (s + s). This string of length 2n contains all possible rotations of s as substrings of length n.
Create two helper arrays, mismatches1 and mismatches2, each of length 2n.
- mismatches1[i] is 1 if s_double[i] differs from the "0101..." pattern at index i, 0 otherwise.
- mismatches2[i] is 1 if s_double[i] differs from the "1010..." pattern at index i, 0 otherwise.
Initialize flips1 and flips2 by summing the first n elements of mismatches1 and mismatches2, respectively. This gives the flip counts for the original, un-rotated string.
Initialize min_flips = min(flips1, flips2).
Iterate from i = 1 to n-1 to slide a window of size n across s_double.
- In each step, update flips1 and flips2 in O(1) time by subtracting the mismatch value of the character leaving the window and adding the mismatch value of the character entering the window.
- The characters are s_double[i-1] (leaving) and s_double[i+n-1] (entering).
- After each update, update min_flips = min(min_flips, flips1, flips2).
Return min_flips.

Walkthrough

This optimized method avoids the O(N^2) complexity by recognizing that rotations can be viewed as a sliding window.

Doubled String: We first create a string s_double of length 2n by appending s to itself. Any cyclic shift of s will appear as a substring of length n in s_double.
Mismatch Arrays: We define two target alternating patterns that extend to length 2n: target1 = "0101..." and target2 = "1010...". We then create two boolean/integer arrays, mismatches1 and mismatches2, where mismatches1[i] is 1 if s_double[i] does not match target1[i], and similarly for mismatches2. This takes O(N) time.
Sliding Window Sum: We calculate the number of flips for the first window (the original string s) by summing the first n elements of the mismatch arrays. Then, we slide the window one position at a time. For each slide, we update the flip counts in O(1) by subtracting the mismatch of the outgoing element and adding the mismatch of the incoming element. For each window, we find the minimum of the two flip counts and update our global minimum.

An important insight is that for any window starting at index i, the minimum flips will be min(current_flips1, current_flips2), where current_flips1 and current_flips2 are the sums of the mismatch arrays over that window. This holds true regardless of the parity of i because if the starting index i has a different parity, the roles of the two target patterns effectively swap, but the minimum of the two costs remains the same.

1class Solution {2    public int minFlips(String s) {3        int n = s.length();4        String s2 = s + s;5        int len2 = 2 * n;6        7        // Mismatches for target "0101..." (pattern1)8        int[] mismatches1 = new int[len2];9        // Mismatches for target "1010..." (pattern2)10        int[] mismatches2 = new int[len2];11        12        for (int i = 0; i < len2; i++) {13            if (s2.charAt(i) != (i % 2 == 0 ? '0' : '1')) {14                mismatches1[i] = 1;15            }16            if (s2.charAt(i) != (i % 2 == 0 ? '1' : '0')) {17                mismatches2[i] = 1;18            }19        }20        21        int flips1 = 0; // Flips for the current window vs pattern122        int flips2 = 0; // Flips for the current window vs pattern223        24        // Calculate flips for the initial window (the original string)25        for (int i = 0; i < n; i++) {26            flips1 += mismatches1[i];27            flips2 += mismatches2[i];28        }29        30        int minFlips = Math.min(flips1, flips2);31        32        // Slide the window across the doubled string33        for (int i = 1; i < n; i++) {34            // Update flip counts in O(1)35            flips1 = flips1 - mismatches1[i - 1] + mismatches1[i + n - 1];36            flips2 = flips2 - mismatches2[i - 1] + mismatches2[i + n - 1];37            38            minFlips = Math.min(minFlips, Math.min(flips1, flips2));39        }40        41        return minFlips;42    }43}

Complexity

Time

O(N), where N is the length of the string. We iterate through the `2n` length string once to build mismatch arrays and then iterate `n` times for the sliding window, resulting in a linear time complexity.

Space

O(N), where N is the length of the string. This space is required to store the doubled string `s_double` and the two mismatch arrays.

Trade-offs

Pros

Optimal time complexity of O(N), making it very efficient for large inputs.
Solves the problem elegantly by transforming the rotation problem into a sliding window problem.

Cons

Requires O(N) extra space, which might be a consideration for extremely large N in a memory-constrained environment.
The logic, while efficient, is less direct than the brute-force approach and requires careful handling of indices and patterns.

Solutions

Solution

1class Solution {2public3  int minFlips(String s) {4    int n = s.length();5    String target = "01";6    int cnt = 0;7    for (int i = 0; i < n; ++i) {8      if (s.charAt(i) != target.charAt(i & 1)) {9        ++cnt;10      }11    }12    int ans = Math.min(cnt, n - cnt);13    for (int i = 0; i < n; ++i) {14      if (s.charAt(i) != target.charAt(i & 1)) {15        --cnt;16      }17      if (s.charAt(i) != target.charAt((i + n) & 1)) {18        ++cnt;19      }20      ans = Math.min(ans, Math.min(cnt, n - cnt));21    }22    return ans;23  }24}

1class Solution {2public:3  int minFlips(string s) {4    int n = s.size();5    string target = "01";6    int cnt = 0;7    for (int i = 0; i < n; ++i) {8      if (s[i] != target[i & 1]) {9        ++cnt;10      }11    }12    int ans = min(cnt, n - cnt);13    for (int i = 0; i < n; ++i) {14      if (s[i] != target[i & 1]) {15        --cnt;16      }17      if (s[i] != target[(i + n) & 1]) {18        ++cnt;19      }20      ans = min({ans, cnt, n - cnt});21    }22    return ans;23  }24};

1class Solution:2    def minFlips(self, s: str) -> int: n = len(s) target = "01" cnt = sum(c != target[i & 1] for i, c in enumerate(s)) ans = min(cnt, n - cnt) for i in range(n): cnt -= s[i] != target[i & 1] cnt += s[i] != target[(i + n) & 1] ans = min(ans, cnt, n - cnt) return ans

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem