Minimum Changes To Make Alternating Binary String solution and explanation
IBM
9 more videos on this problem
Minimum Changes To Make Alternating Binary String - Leetcode 1758 - PythonNeetCodeIO · 5:54 · 16K views
Minimum Changes To Make Alternating Binary String | 2 Approaches | MICROSOFT | Leetcode 1758 | MIKcodestorywithMIK · 25:14 · 10K views
Minimum Changes for Alternating Binary String | LeetCode 1758 | Complementary Counting StrategySanyam IIT Guwahati · 7:04 · 1K views
Leetcode | 1758. Minimum Changes To Make Alternating Binary String | Easy | Java SolutionDeveloper Docs · 7:46 · 622 views
1758. Minimum Changes To Make Alternating Binary String | Leetcode Daily - PythonLeetcode Daily · 6:34 · 374 views
Daily Leetcode #2165: Mar 05, 2026 - 1758. Minimum Changes To Make Alternating Binary StringProgramming Live with Larry · 3:36 · 310 views
Minimum Changes To Make Alternating Binary String | LeetCode 1758 | Java Code | Developer CoderDeveloper Coder · 13:21 · 244 views
LeetCode 1758 | Easy | Minimum Changes To Make Alternating Binary StringUtshaw · 7:52 · 150 views
Solving LeetCode 1758 Minimum Changes To Make Alternating Binary String | Adobe Interview QuestionCode Harmony · 12:20 · 131 views
Minimum Changes To Make Alternating Binary String | LeetCode 1758 - Pythonimpoldev · 5:26 · 122 views
The problem
You are given a string s consisting only of the characters '0' and '1'. In one operation, you can change any '0' to '1' or vice versa.
The string is called alternating if no two adjacent characters are equal. For example, the string "010" is alternating, while the string "0100" is not.
Return the minimum number of operations needed to make s alternating.
Example 1:
Input: s = "0100" Output: 1 Explanation: If you change the last character to '1', s will be "0101", which is alternating.
Example 2:
Input: s = "10" Output: 0 Explanation: s is already alternating.
Example 3:
Input: s = "1111" Output: 2 Explanation: You need two operations to reach "0101" or "1010".
Constraints:
1 <= s.length <= 104s[i]is either'0'or'1'.
Approach overview
Problem Overview: You are given a binary string s. The goal is to determine the minimum number of character flips required to transform it into an alternating string. An alternating binary string has no two adjacent characters equal, meaning it must follow either the pattern 010101... or 101010....
The key observation: only two valid alternating patterns exist for any length. If you compare the input string against both patterns and count mismatches, the smaller mismatch count gives the minimum number of flips needed.
Approach 1: Compare to Two Patterns (O(n) time, O(1) space)
Iterate through the string once while comparing each character with the expected character for two possible patterns: one starting with '0' (0101...) and one starting with '1' (1010...). For index i, the expected character depends on parity: even indices match the starting bit, odd indices match the opposite bit. Maintain two counters for mismatches—one for each pattern. Each time s[i] differs from the expected character, increment the corresponding counter. After scanning the entire string, return the smaller mismatch count.
This approach uses a simple string traversal with constant bookkeeping. No additional data structures are required. The algorithm runs in O(n) time because each character is processed exactly once, and it uses O(1) space since only two counters are maintained. This is the most common solution in interviews and production code because it is both minimal and easy to reason about.
Approach 2: Precomputed Masks (O(n) time, O(n) space)
Another way to solve the problem is to explicitly build the two target alternating strings of the same length as s. Construct one mask mask1 = "0101..." and another mask2 = "1010...". Then iterate through the original string and count the number of positions where s[i] differs from each mask. The minimum mismatch count between the two masks represents the number of flips needed.
This approach still performs a single pass over the string, giving O(n) time complexity. However, it allocates additional memory for the two mask strings, resulting in O(n) space complexity. The logic is straightforward and sometimes easier for beginners because the expected pattern is explicitly represented rather than computed dynamically.
Recommended for interviews: The two-pattern comparison approach is the expected solution. It demonstrates strong reasoning about string patterns and avoids unnecessary memory allocation. The mask approach shows correct thinking but adds extra space without improving runtime. Interviewers typically look for the constant-space scan because it proves you recognized that only two alternating patterns are possible.
Approach 1: Compare to Two Patterns
The aim here is to transform the given string into either "010101..." or "101010...", as these are the only two possible alternating patterns for a binary string. By comparing the given string to these patterns, we can determine the minimum number of operations required.
We create these patterns for the length of the string and then count mismatches for both patterns by iterating through the string.
def minOperations(s: str) -> int:
pattern1 = pattern2 = 0
for i in range(len(s)):
if s[i] != ('0' if i % 2 == 0 else '1'):
pattern1 += 1
if s[i] != ('1' if i % 2 == 0 else '0'):
pattern2 += 1
return min(pattern1, pattern2)
s = "0100"
print(minOperations(s))public class AlternatingString {
public static int minOperations(String s) {
int pattern1 = 0, pattern2 = 0;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) != (i % 2 == 0 ? '0' : '1')) pattern1++;
if (s.charAt(i) != (i % 2 == 0 ? '1' : '0')) pattern2++;
}
return Math.min(pattern1, pattern2);
}
public static void main(String[] args) {
String s = "0100";
System.out.println(minOperations(s));
}
}#include <string>
#include <iostream>
int minOperations(const std::string& s) {
int len = s.length();
int pattern1 = 0, pattern2 = 0;
for (int i = 0; i < len; i++) {
if (s[i] != (i % 2 == 0 ? '0' : '1')) pattern1++;
if (s[i] != (i % 2 == 0 ? '1' : '0')) pattern2++;
}
return std::min(pattern1, pattern2);
}
int main() {
std::string s = "0100";
std::cout << minOperations(s) << std::endl;
return 0;
}function minOperations(s) {
let pattern1 = 0, pattern2 = 0;
for (let i = 0; i < s.length; i++) {
if (s[i] !== (i % 2 === 0 ? '0' : '1')) pattern1++;
if (s[i] !== (i % 2 === 0 ? '1' : '0')) pattern2++;
}
return Math.min(pattern1, pattern2);
}
const s = "0100";
console.log(minOperations(s));#include <stdio.h>
#include <string.h>
int minOperations(char *s) {
int len = strlen(s);
int pattern1 = 0, pattern2 = 0;
for (int i = 0; i < len; i++) {
if (s[i] != (i % 2 == 0 ? '0' : '1')) pattern1++;
if (s[i] != (i % 2 == 0 ? '1' : '0')) pattern2++;
}
return pattern1 < pattern2 ? pattern1 : pattern2;
}
int main() {
char s[] = "0100";
printf("%d\n", minOperations(s));
return 0;
}using System;
public class AlternatingString {
public static int MinOperations(string s) {
int pattern1 = 0, pattern2 = 0;
for (int i = 0; i < s.Length; i++) {
if (s[i] != (i % 2 == 0 ? '0' : '1')) pattern1++;
if (s[i] != (i % 2 == 0 ? '1' : '0')) pattern2++;
}
return Math.Min(pattern1, pattern2);
}
public static void Main() {
string s = "0100";
Console.WriteLine(MinOperations(s));
}
}This Python function compares the input string against two possible alternating patterns by counting mismatches through a single iteration over the string. It returns the minimum operation count needed to transform the given string.
Time Complexity: O(n).
Space Complexity: O(1).
Approach 2: Precomputed Masks
This method involves precomputing two mask strings that represent the possible alternating strings for any given length. We perform a comparison between the string and both masks, incrementing a counter for each mismatch, and outputting the smaller of the two.
def minOperations(s: str) -> int:
len_s = len(s)
mask1 = ''.join('0' if i % 2 == 0 else '1' for i in range(len_s))
mask2 = ''.join('1' if i % 2 == 0 else '0' for i in range(len_s))
count1 = sum(1 for i in range(len_s) if s[i] != mask1[i])
count2 = sum(1 for i in range(len_s) if s[i] != mask2[i])
return min(count1, count2)
s = "0100"
print(minOperations(s))public class AlternatingString {
public static int minOperations(String s) {
int len = s.length();
StringBuilder mask1 = new StringBuilder(len);
StringBuilder mask2 = new StringBuilder(len);
for (int i = 0; i < len; i++) {
mask1.append(i % 2 == 0 ? '0' : '1');
mask2.append(i % 2 == 0 ? '1' : '0');
}
int count1 = 0, count2 = 0;
for (int i = 0; i < len; i++) {
if (s.charAt(i) != mask1.charAt(i)) count1++;
if (s.charAt(i) != mask2.charAt(i)) count2++;
}
return Math.min(count1, count2);
}
public static void main(String[] args) {
String s = "0100";
System.out.println(minOperations(s));
}
}#include <string>
#include <iostream>
int minOperations(const std::string& s) {
int len = s.length();
std::string mask1(len, '0'), mask2(len, '1');
for (int i = 0; i < len; i++) {
mask1[i] = i % 2 == 0 ? '0' : '1';
mask2[i] = i % 2 == 0 ? '1' : '0';
}
int count1 = 0, count2 = 0;
for (int i = 0; i < len; i++) {
if (s[i] != mask1[i]) count1++;
if (s[i] != mask2[i]) count2++;
}
return std::min(count1, count2);
}
int main() {
std::string s = "0100";
std::cout << minOperations(s) << std::endl;
return 0;
}function minOperations(s) {
const len = s.length;
const mask1 = Array(len).fill(0).map((_, i) => i % 2 === 0 ? '0' : '1').join('');
const mask2 = Array(len).fill(0).map((_, i) => i % 2 === 0 ? '1' : '0').join('');
let count1 = 0, count2 = 0;
for (let i = 0; i < len; i++) {
if (s[i] !== mask1[i]) count1++;
if (s[i] !== mask2[i]) count2++;
}
return Math.min(count1, count2);
}
const s = "0100";
console.log(minOperations(s));#include <stdio.h>
#include <string.h>
int minOperations(char *s) {
int len = strlen(s);
char mask1[len+1], mask2[len+1];
for (int i = 0; i < len; i++) {
mask1[i] = i % 2 == 0 ? '0' : '1';
mask2[i] = i % 2 == 0 ? '1' : '0';
}
mask1[len] = '\0';
mask2[len] = '\0';
int count1 = 0, count2 = 0;
for (int i = 0; i < len; i++) {
if (s[i] != mask1[i]) count1++;
if (s[i] != mask2[i]) count2++;
}
return count1 < count2 ? count1 : count2;
}
int main() {
char s[] = "0100";
printf("%d\n", minOperations(s));
return 0;
}using System;
using System.Text;
public class AlternatingString {
public static int MinOperations(string s) {
int len = s.Length;
StringBuilder mask1 = new StringBuilder(len);
StringBuilder mask2 = new StringBuilder(len);
for (int i = 0; i < len; i++) {
mask1.Append(i % 2 == 0 ? '0' : '1');
mask2.Append(i % 2 == 0 ? '1' : '0');
}
int count1 = 0, count2 = 0;
for (int i = 0; i < len; i++) {
if (s[i] != mask1[i]) count1++;
if (s[i] != mask2[i]) count2++;
}
return Math.Min(count1, count2);
}
public static void Main() {
string s = "0100";
Console.WriteLine(MinOperations(s));
}
}This Python solution constructs two mask strings directly and compares them with the original string to calculate required changes. The solution then returns the minimum of these counts.
Time Complexity: O(n).
Space Complexity: O(n) for mask generation.
Approach 3: Single Pass
According to the problem, if the number of operations needed to obtain the alternating string 01010101... is cnt, then the number of operations needed to obtain the alternating string 10101010... is n - cnt.
Therefore, we only need to traverse the string s once, count the value of cnt, and the answer is min(cnt, n - cnt).
The time complexity is O(n), where n is the length of the string s. The space complexity is O(1).
function minOperations(s: string): number {
let cnt = 0;
const n = s.length;
for (let i = 0; i < n; ++i) {
if (s[i] !== '01'[i & 1]) {
++cnt;
}
}
return Math.min(cnt, n - cnt);
}func minOperations(s string) int {
cnt := 0
for i, c := range s {
if c != []rune("01")[i&1] {
cnt++
}
}
return min(cnt, len(s)-cnt)
}impl Solution {
pub fn min_operations(s: String) -> i32 {
let mut cnt: i32 = 0;
let n: i32 = s.len() as i32;
let bytes = s.as_bytes();
for i in 0..n as usize {
if bytes[i] != b"01"[i & 1] {
cnt += 1;
}
}
cnt.min(n - cnt)
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Compare to Two Patterns | Time Complexity: O(n). |
| Precomputed Masks | Time Complexity: O(n). |
| Single Pass | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Compare to Two Patterns | O(n) | O(1) | Best general solution. Single pass with constant memory. |
| Precomputed Masks | O(n) | O(n) | Useful for clarity when explicitly comparing with target patterns. |
Frequently asked questions
Is Minimum Changes To Make Alternating Binary String easy or hard?
Minimum Changes To Make Alternating Binary String is classified as an Easy problem on LeetCode with an acceptance rate around 67%. The main challenge is recognizing that only two valid alternating patterns exist, which simplifies the solution to a single pass comparison.
Minimum Changes To Make Alternating Binary String Python/Java solution
In both Python and Java, the solution iterates through the string and compares each character with the expected value for two alternating patterns. Maintain two mismatch counters and return the smaller one. The implementation is concise and runs in O(n) time with O(1) extra space.
How to solve Minimum Changes To Make Alternating Binary String in O(n)?
Scan the string once and compare each character with the expected value for two patterns: one starting with '0' and the other starting with '1'. Maintain mismatch counts for both cases. At the end of the traversal, return the minimum of the two counts. This requires one pass and constant additional memory.
What is the best approach for Minimum Changes To Make Alternating Binary String?
The best approach is comparing the string against the two possible alternating patterns: "0101..." and "1010...". Iterate once through the string and count mismatches for both patterns. The smaller mismatch count is the answer. This solution runs in O(n) time and O(1) space.
Is Minimum Changes To Make Alternating Binary String asked at Google/Amazon/Meta?
Alternating pattern and string mismatch problems appear frequently in coding interviews at companies like Amazon, Google, and Meta. While this exact question may not always appear, the pattern-recognition technique and single-pass counting strategy are commonly tested in string and greedy interview questions.
What data structure is used in Minimum Changes To Make Alternating Binary String?
The problem primarily uses basic string traversal. No complex data structures are required. The optimal solution maintains simple counters while iterating through the string and comparing characters with expected alternating values.
What is the time complexity of Minimum Changes To Make Alternating Binary String?
The optimal solution runs in O(n) time where n is the length of the binary string. Each character is checked exactly once while comparing it with the expected alternating pattern. Space complexity is O(1) because only two mismatch counters are maintained.