Minimum Changes To Make Alternating Binary String
EasyPrompt
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'.
Approaches
3 approaches with complexity analysis and trade-offs.
This approach involves creating the two possible alternating target strings ("0101..." and "1010...") and then comparing the input string with each of them. The number of changes required for each target is the count of differing characters. The minimum of these two counts is the answer.
Algorithm
- Get the length
nof the input strings. - Create two
StringBuilderobjects,target1Builderandtarget2Builder. - Loop from
i = 0ton-1. In each iteration, append the correct alternating character to both builders.target1Buildergets '0' at even indices and '1' at odd indices.target2Buildergets '1' at even indices and '0' at odd indices. - Convert the builders to strings
target1andtarget2. - Initialize two counters,
changes1andchanges2, to 0. - Loop from
i = 0ton-1.- Compare
s.charAt(i)withtarget1.charAt(i). If they are different, incrementchanges1. - Compare
s.charAt(i)withtarget2.charAt(i). If they are different, incrementchanges2.
- Compare
- Return the minimum of
changes1andchanges2.
Walkthrough
The core idea is to materialize the two goal states. Any alternating binary string must either start with '0' or '1'.
- First, we construct a string
target1that starts with '0' (e.g., "0101..."). - Second, we construct another string
target2that starts with '1' (e.g., "1010..."). - Then, we iterate through the input string
sand count how many characters need to be flipped to matchtarget1. Let's call thiscost1. - We do the same for
target2to getcost2. - The final answer is the smaller value between
cost1andcost2.
class Solution { public int minOperations(String s) { int n = s.length(); StringBuilder target1Builder = new StringBuilder(); StringBuilder target2Builder = new StringBuilder(); for (int i = 0; i < n; i++) { if (i % 2 == 0) { target1Builder.append('0'); target2Builder.append('1'); } else { target1Builder.append('1'); target2Builder.append('0'); } } String target1 = target1Builder.toString(); String target2 = target2Builder.toString(); int changes1 = 0; int changes2 = 0; for (int i = 0; i < n; i++) { if (s.charAt(i) != target1.charAt(i)) { changes1++; } if (s.charAt(i) != target2.charAt(i)) { changes2++; } } return Math.min(changes1, changes2); }}Complexity
Time
O(n), where n is the length of the string. We have three loops that each run n times: one to build the target strings, and two implicit loops within the final comparison loop. This simplifies to O(n).
Space
O(n) to store the two generated target strings.
Trade-offs
Pros
Simple to understand and implement.
The logic directly follows the problem definition.
Cons
Uses extra space proportional to the length of the input string to store the two target strings.
Less efficient than single-pass solutions that don't require extra storage.
This approach improves upon the brute-force method by avoiding the creation of the target strings. Instead of pre-building the target strings, we can determine the expected character at each position on-the-fly during a single pass through the input string. We maintain two counters to track the number of changes needed for each of the two possible alternating patterns.
Algorithm
- Initialize two counters,
changes1(for "0101..." pattern) andchanges2(for "1010..." pattern), to 0. - Iterate through the input string
swith indexifrom 0 ton-1. - Inside the loop, check if
iis even or odd. - If
iis even:- The "0101..." pattern expects '0'. If
s.charAt(i)is '1', incrementchanges1. - The "1010..." pattern expects '1'. If
s.charAt(i)is '0', incrementchanges2.
- The "0101..." pattern expects '0'. If
- If
iis odd:- The "0101..." pattern expects '1'. If
s.charAt(i)is '0', incrementchanges1. - The "1010..." pattern expects '0'. If
s.charAt(i)is '1', incrementchanges2.
- The "0101..." pattern expects '1'. If
- After the loop, return
Math.min(changes1, changes2).
Walkthrough
We can iterate through the string s just once. At each index i, we know what the character should be for both alternating patterns.
- For the pattern starting with '0' ("0101..."), the character at index
ishould be '0' ifiis even, and '1' ifiis odd. - For the pattern starting with '1' ("1010..."), the character at index
ishould be '1' ifiis even, and '0' ifiis odd. - We use two variables,
cost1andcost2, to count the mismatches for each pattern. We iterate fromi = 0ton-1and update the counters based on the characters.charAt(i). - Finally, we return
min(cost1, cost2). This eliminates the need for O(n) extra space.
class Solution { public int minOperations(String s) { int n = s.length(); int changes1 = 0; // Cost for pattern "0101..." int changes2 = 0; // Cost for pattern "1010..." for (int i = 0; i < n; i++) { // Check for pattern "0101..." if (i % 2 == 0) { // Even index, should be '0' if (s.charAt(i) == '1') { changes1++; } } else { // Odd index, should be '1' if (s.charAt(i) == '0') { changes1++; } } // Check for pattern "1010..." if (i % 2 == 0) { // Even index, should be '1' if (s.charAt(i) == '0') { changes2++; } } else { // Odd index, should be '0' if (s.charAt(i) == '1') { changes2++; } } } return Math.min(changes1, changes2); }}Complexity
Time
O(n), as we iterate through the string once.
Space
O(1), as we only use a few integer variables for counters, regardless of the input size.
Trade-offs
Pros
Space-efficient, using only a constant amount of extra space.
Still conceptually simple and easy to follow.
Cons
The logic inside the loop is slightly more complex than the most optimal solution, with multiple conditional checks per iteration.
This is the most efficient approach. It builds on a key observation: the two target alternating strings ("0101..." and "1010...") are exact complements of each other. This means that if a character in the input string matches one pattern at a certain position, it must mismatch the other. Therefore, the sum of changes for both patterns is always equal to the length of the string (n). We only need to calculate the cost for one pattern and can derive the other.
Algorithm
- Get the length
nof the input strings. - Initialize a single counter,
changes, to 0. This counter will track the cost to transformsinto the pattern starting with '0' ("0101..."). - Iterate through the string
swith indexifrom 0 ton-1. - In each iteration, determine the expected character for the "0101..." pattern. If
iis even, it's '0'; ifiis odd, it's '1'. - Compare
s.charAt(i)with the expected character. If they don't match, incrementchanges. - After the loop,
changesholds the cost for one pattern. The cost for the other pattern isn - changes. - Return
Math.min(changes, n - changes).
Walkthrough
Let cost1 be the number of operations to make the string "0101..." and cost2 be the number of operations to make it "1010...".
- At any index
i, ifs[i]matches the character for the "0101..." pattern, it will not match the character for the "1010..." pattern, and vice-versa. - This implies that for every index, there is exactly one mismatch when considering both patterns together.
- Summing over all indices, the total number of mismatches is
cost1 + cost2 = n, wherenis the length of the string. - So, we can calculate just one of the costs, say
cost1, by iterating through the string once. Then,cost2is simplyn - cost1. The minimum operations will bemin(cost1, n - cost1). - This simplifies the logic within the loop and reduces the number of comparisons.
class Solution { public int minOperations(String s) { int n = s.length(); int changes = 0; // Cost for pattern starting with '0' ("0101...") for (int i = 0; i < n; i++) { char expectedChar = (i % 2 == 0) ? '0' : '1'; if (s.charAt(i) != expectedChar) { changes++; } } // The cost for the other pattern ("1010...") is n - changes. // We need the minimum of the two. return Math.min(changes, n - changes); }}Complexity
Time
O(n), for a single pass over the string.
Space
O(1), as it only requires a single counter variable.
Trade-offs
Pros
Most efficient in terms of both time and space.
O(1) space complexity.
O(n) time complexity with the minimum number of operations per iteration.
The code is clean and concise.
Cons
Relies on a clever observation (
cost1 + cost2 = n) which might not be immediately obvious.
Solutions
Solution
class Solution {public int minOperations(String s) { int cnt = 0, n = s.length(); for (int i = 0; i < n; ++i) { cnt += (s.charAt(i) != "01".charAt(i & 1) ? 1 : 0); } return Math.min(cnt, n - cnt); }}class Solution {public: int minOperations(string s) { int cnt = 0, n = s.size(); for (int i = 0; i < n; ++i) cnt += s[i] != "01"[i & 1]; return min(cnt, n - cnt); }};class Solution: def minOperations(self, s: str) -> int: cnt = sum(c != '01' [i & 1] for i, c in enumerate(s)) return min(cnt, len(s) - cnt)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.