#1758

Easy

auto_awesomeString-driven solution strategy

LeetCode Problem Workspace

Minimum Changes To Make Alternating Binary String

Find the minimum number of changes required to convert a string into an alternating binary string.

Problem Statement

You are given a binary string s consisting of '0' and '1'. In one operation, you can change any character to '0' or '1'. A binary string is considered alternating if no two adjacent characters are the same. For example, '010' is alternating, but '0100' is not.

Your goal is to determine the minimum number of operations needed to transform s into an alternating string, either starting with '0' or '1'.

Examples

Example 1

Input: s = "0100"

Output: 1

If you change the last character to '1', s will be "0101", which is alternating.

Example 2

Input: s = "10"

Output: 0

s is already alternating.

Example 3

Input: s = "1111"

Output: 2

You need two operations to reach "0101" or "1010".

Constraints

1 <= s.length <= 104
s[i] is either '0' or '1'.

Solution Approach

Two possible alternating patterns

There are two possible alternating patterns: one starting with '0' ('010101...') and another starting with '1' ('101010...'). Compare the given string with both patterns to calculate the number of mismatches.

Count mismatches

For each of the two patterns, iterate through the string and count how many characters differ from the expected value. The minimum number of mismatches will give the minimum number of operations needed.

Return minimum operations

Once the mismatches for both patterns are counted, return the smaller of the two counts as the answer, as it represents the fewest changes required to make the string alternating.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(1)

The time complexity is O(n) since we only iterate through the string once to count mismatches for both patterns. The space complexity is O(1) because we use a constant amount of extra space for counting mismatches.

What Interviewers Usually Probe

The candidate can identify and count mismatches efficiently.
The candidate recognizes that there are only two possible alternating patterns to consider.
The candidate applies a linear time complexity approach to solve the problem.

Common Pitfalls or Variants

Common pitfalls

Failing to consider both possible alternating patterns.
Not efficiently counting mismatches, leading to excessive time complexity.
Confusing the concept of alternating strings with other string patterns, missing the specific alternating condition.

Follow-up variants

Modify the problem to consider strings with additional characters or constraints.
Extend the problem to allow other operations besides changing characters.
Challenge candidates with larger input sizes and more complex constraints.

FAQ

What is the minimum number of changes needed for the string '0100'?

To make the string '0100' alternating, you need to change the last character to '1', resulting in the string '0101', which takes 1 change.

How do I approach this problem?

Think about how the string will look after transformations. There are only two possible alternating patterns, and you need to find the pattern with the least number of mismatches.

What are the two alternating patterns to compare with?

The two alternating patterns to consider are '010101...' and '101010...'. Compare the given string to both of these patterns to count mismatches.

How do I optimize the solution for larger strings?

By using a linear scan to count mismatches for both alternating patterns, the time complexity remains O(n), ensuring the solution scales well for larger strings.

What is the time complexity of the solution?

The time complexity is O(n) since we only need to iterate through the string once to count mismatches for both possible alternating patterns.

terminal

Solution

Solution 1: Single Pass

According to the problem, if the number of operations needed to obtain the alternating string `01010101...` is $\textit{cnt}$, then the number of operations needed to obtain the alternating string `10101010...` is $n - \textit{cnt}$.

1

2

3

4

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)

Continue Practicing

#1759 count number of homogenous substrings #1754 largest merge of two strings #1763 longest nice substring