Minimum Number of Flips to Make the Binary String Alternating

Minimum Number of Flips to Make the Binary String Alternating - Problem

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.

Input & Output

Example 1 — Basic Case

$ Input: s = "11000"

› Output: 1

💡 Note: We can rotate to get "00011" or "01100", then flip 1 character to make it alternating like "01010" or "10101".

Example 2 — Already Alternating After Rotation

$ Input: s = "10"

› Output: 0

💡 Note: The string is already alternating, so no type-2 operations (flips) are needed.

Example 3 — Single Character

$ Input: s = "1"

› Output: 0

💡 Note: A single character is always alternating by definition.

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input

Binary string "11000" that needs to become alternating

Rotate + Flip

Try different rotations and count minimum flips needed

Output

Minimum number of type-2 operations (flips) required

Key Takeaway

🎯 Key Insight: Try all possible rotations and find the one requiring minimum flips to become alternating

Asked in

M Meta 15 G Google 12 M Microsoft 8

The key insight is that we can rotate the string to any position and then count flips needed for alternating patterns. The optimal approach uses incremental cost updates when simulating rotations, achieving O(n) time complexity instead of O(n²).

Common Approaches

Approach	Time	Space	Notes
✓ Optimized with Precomputation	O(n)	O(1)	Use difference arrays to calculate rotation costs in O(1) time each
Sliding Window Optimization	O(n²)	O(n)	Use sliding window to efficiently calculate flip costs for all rotations
Brute Force - Try All Rotations	O(n²)	O(n)	Try every possible rotation of the string and calculate flip cost for each

Optimized with Precomputation — Algorithm Steps

Calculate initial costs for both alternating patterns
For each rotation, update costs based on character movement
Use the fact that rotation changes are predictable
Track minimum across all rotations

Visualization

Tap to expand

Step-by-Step Walkthrough

Initial Cost

Calculate flip cost for original string

Update Formula

When rotating, update cost based on moved character

Track Minimum

Keep track of minimum cost across all rotations

Code -

solution.c — C

#include <stdio.h>
#include <string.h>
#include <limits.h>

int solution(char* s) {
    int n = strlen(s);
    if (n == 1) return 0;
    
    // Calculate initial flip costs for both patterns
    int cost0 = 0;  // Cost if pattern starts with '0'
    int cost1 = 0;  // Cost if pattern starts with '1'
    
    for (int i = 0; i < n; i++) {
        char expected0 = i % 2 == 0 ? '0' : '1';
        char expected1 = i % 2 == 0 ? '1' : '0';
        
        if (s[i] != expected0) cost0++;
        if (s[i] != expected1) cost1++;
    }
    
    int minFlips = cost0 < cost1 ? cost0 : cost1;
    
    // Try all rotations by updating costs incrementally
    for (int rotation = 1; rotation < n; rotation++) {
        // Character moving from front to back
        char ch = s[rotation - 1];
        
        // Update cost for pattern starting with '0'
        char frontExpected0 = (rotation - 1) % 2 == 0 ? '0' : '1';
        if (ch != frontExpected0) cost0--;
        
        char backExpected0 = (n - 1) % 2 == 0 ? '0' : '1';
        if (ch != backExpected0) cost0++;
        
        // Update cost for pattern starting with '1'
        char frontExpected1 = (rotation - 1) % 2 == 0 ? '1' : '0';
        if (ch != frontExpected1) cost1--;
        
        char backExpected1 = (n - 1) % 2 == 0 ? '1' : '0';
        if (ch != backExpected1) cost1++;
        
        int currentMin = cost0 < cost1 ? cost0 : cost1;
        if (currentMin < minFlips) minFlips = currentMin;
    }
    
    return minFlips;
}

int main() {
    char s[1001];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0; // Remove newline
    
    int result = solution(s);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass to calculate initial costs, then O(1) updates for each rotation

✓ Linear Growth

Space Complexity

O(1)

Only using a few variables to track costs and minimum

✓ Linear Space

28.4K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Optimized with Precomputation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler