Scale Engineer

Minimum Changes To Make Alternating Binary String

Easy
#1609Time: 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.1 company
Data structures
String
Companies
Tesla

Prompt

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 <= 104
  • s[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 n of the input string s.
  • Create two StringBuilder objects, target1Builder and target2Builder.
  • Loop from i = 0 to n-1. In each iteration, append the correct alternating character to both builders. target1Builder gets '0' at even indices and '1' at odd indices. target2Builder gets '1' at even indices and '0' at odd indices.
  • Convert the builders to strings target1 and target2.
  • Initialize two counters, changes1 and changes2, to 0.
  • Loop from i = 0 to n-1.
    • Compare s.charAt(i) with target1.charAt(i). If they are different, increment changes1.
    • Compare s.charAt(i) with target2.charAt(i). If they are different, increment changes2.
  • Return the minimum of changes1 and changes2.

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 target1 that starts with '0' (e.g., "0101...").
  • Second, we construct another string target2 that starts with '1' (e.g., "1010...").
  • Then, we iterate through the input string s and count how many characters need to be flipped to match target1. Let's call this cost1.
  • We do the same for target2 to get cost2.
  • The final answer is the smaller value between cost1 and cost2.
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.

Solutions

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);  }}

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 →

Next problem