Logo

Kode$word

Minimum Changes to Make Alternating Binary String – LeetCode 1758 Explained
Minimum Changes to Make Alternating Binary String – LeetCode 1758 Explained

Minimum Changes to Make Alternating Binary String – LeetCode 1758 Explained

Understand how to convert a binary string into an alternating pattern with the minimum number of flips using a simple greedy approach.

19 views
0
0
LeetCodeBinary StringGreedy AlgorithmJavaEasy
Github icon

Try This Question

Before reading the solution, try solving the problem yourself on LeetCode:

👉 https://leetcode.com/problems/minimum-changes-to-make-alternating-binary-string/


Problem Statement

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

In one operation, you can change any '0' to '1' or '1' to '0'.

A string is called alternating if no two adjacent characters are the same.

Example of Alternating Strings

010
101
0101
1010

Example of Non-Alternating Strings

00
0100
111
1101

Your task is to return the minimum number of operations required to make the string alternating.


Example Walkthrough

Example 1

Input

s = "0100"

Possible fix:

0101

Only the last character needs to change, so the answer is:

Output

1

Example 2

Input

s = "10"

The string is already alternating.

Output

0

Example 3

Input

s = "1111"

Possible alternating strings:

0101
1010

Minimum operations needed = 2

Output

2


Key Observation

An alternating binary string can only have two possible patterns:

Pattern 1

0101010101...

Pattern 2

1010101010...

So instead of trying many combinations, we only need to check:

1️⃣ How many changes are required to convert s → "010101..."

2️⃣ How many changes are required to convert s → "101010..."

Then we return the minimum of the two.


Approach

Step 1

Generate two possible alternating strings:

s1 = "010101..."
s2 = "101010..."

Both will be of the same length as the input string.

Step 2

Compare the original string with both patterns.

Count mismatches.

For example:

s = 0100
s1 = 0101

Mismatch count = 1

Step 3

Repeat for the second pattern.

Finally return:

min(mismatch1, mismatch2)


Intuition Behind the Solution

Instead of flipping characters randomly, we compare the string with the two valid alternating possibilities.

Why only two?

Because:

  1. Alternating strings must start with either 0 or 1
  2. After that, the pattern is fixed.

So we simply compute which pattern requires fewer changes.

This makes the solution efficient and simple.


Java Implementation

class Solution {
public int minOperations(String s) {
int co1 = 0;
int co2 = 0;

String s1 = "";
String s2 = "";

for(int i = 0; i < s.length(); i++){
if(i % 2 == 0){
s1 += "0";
} else {
s1 += "1";
}
}

for(int i = 0; i < s.length(); i++){
if(i % 2 == 0){
s2 += "1";
} else {
s2 += "0";
}
}

for(int i = 0; i < s.length(); i++){
if(s.charAt(i) != s1.charAt(i)){
co1++;
}
}

for(int i = 0; i < s.length(); i++){
if(s.charAt(i) != s2.charAt(i)){
co2++;
}
}

return Math.min(co1, co2);
}
}


Complexity Analysis

Time Complexity

O(n)

We iterate through the string a few times.

Space Complexity

O(n)

Because we create two extra strings of size n.


Optimized Approach (Better Interview Answer)

We can avoid creating extra strings and calculate mismatches directly.

Optimized Java Code

class Solution {
public int minOperations(String s) {
int pattern1 = 0;
int pattern2 = 0;

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

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

if(s.charAt(i) != expected1) pattern1++;
if(s.charAt(i) != expected2) pattern2++;
}

return Math.min(pattern1, pattern2);
}
}

Space Complexity Now

O(1)

No extra strings required.


Why This Problem Is Important

This problem teaches important interview concepts:

✔ Pattern observation

✔ Greedy thinking

✔ String manipulation

✔ Optimization techniques

Many companies ask similar pattern-based string problems.


Final Thoughts

The trick in this problem is realizing that only two alternating patterns exist. Once you identify that, the problem becomes straightforward.

Instead of trying multiple modifications, you simply compare and count mismatches.

This leads to a clean and efficient O(n) solution.

If you are preparing for coding interviews, practicing problems like this will improve your pattern recognition skills, which is a key skill for solving medium and hard problems later.


Happy Coding 🚀

Related Articles

Check if Binary String Has at Most One Segment of Ones – Java Solution (LeetCode 1784)

Check if Binary String Has at Most One Segment of Ones – Java Solution (LeetCode 1784)

Learn how to determine whether a binary string contains only one continuous group of 1s. This article explains the problem clearly, builds the intuition step-by-step, and walks through a clean Java solution with time complexity analysis.

Read Article
LeetCode 1980: Find Unique Binary String – Multiple Ways to Generate a Missing Binary Combination

LeetCode 1980: Find Unique Binary String – Multiple Ways to Generate a Missing Binary Combination

A Complete Guide to Solving “Find Unique Binary String” Using Hashing, Brute Force Thinking, and Cantor’s Diagonalization

Read Article
Find Peak Element – Binary Search Explained with Java Solution (LeetCode 162)

Find Peak Element – Binary Search Explained with Java Solution (LeetCode 162)

Learn how to efficiently find a peak element in an array using binary search. This guide explains the problem clearly, builds intuition step-by-step, and walks through multiple approaches with a clean O(log n) solution.

Read Article
LeetCode 121 — Best Time to Buy and Sell Stock I | Two Pointer / Sliding Window Explained

LeetCode 121 — Best Time to Buy and Sell Stock I | Two Pointer / Sliding Window Explained

A beginner-friendly breakdown of the classic stock profit problem — intuition, dry run, commented Java code, and complexity analysis.

Read Article

Ai Assistant Kas