algoadvance

Leetcode 1758. Minimum Changes To Make Alternating Binary String

Problem Statement

The problem is to determine the minimum number of changes needed to make a given binary string an alternating binary string. An alternating binary string is a string where no two adjacent characters are the same, i.e., it follows a pattern like “010101” or “101010”.

Given a binary string s, you need to return the minimum number of changes needed to make the string alternating.

Clarifying Questions

  1. Input Constraints:
    • What is the length range of the string?
      • The length of the string s is between 1 and 100,000.
    • Is the string guaranteed to contain only characters ‘0’ and ‘1’?
      • Yes, the string contains only characters ‘0’ and ‘1’.
  2. Output:
    • Should we return just the minimum number of changes or the modified string as well?
      • The minimum number of changes.

Strategy

To solve this problem efficiently:

  1. Pattern Analysis:
    • We need to determine the number of changes required to convert the string s into two possible alternating patterns:
      • Pattern1: “010101…”
      • Pattern2: “101010…”
  2. Count Mismatches:
    • Iterate through the string, comparing it with both patterns and count mismatches for each.
    • For Pattern1, the characters at even indices should be ‘0’ and at odd indices should be ‘1’.
    • For Pattern2, the characters at even indices should be ‘1’ and at odd indices should be ‘0’.
  3. Result Calculation:
    • The result will be the minimum of the two mismatch counts.

Code

Here’s the C++ implementation of the solution:

#include <iostream>
#include <string>
#include <algorithm>

int minChangesToMakeAlternatingBinaryString(std::string s) {
    int n = s.length();
    int count1 = 0, count2 = 0;
    
    for (int i = 0; i < n; ++i) {
        if ((i % 2 == 0 && s[i] != '0') || (i % 2 == 1 && s[i] != '1')) {
            count1++;
        }
        if ((i % 2 == 0 && s[i] != '1') || (i % 2 == 1 && s[i] != '0')) {
            count2++;
        }
    }
    
    return std::min(count1, count2);
}

int main() {
    std::string s = "0100100010";
    std::cout << "Minimum changes to make the string alternating: " 
              << minChangesToMakeAlternatingBinaryString(s) << std::endl;
    return 0;
}

Explanation of Code

  1. Initialization: We initialize two counters, count1 and count2, to keep track of mismatches for Pattern1 and Pattern2 respectively.
  2. Loop through the string: For each character in the string, we check if it matches the expected character in both patterns and increment the respective mismatch counter if it doesn’t match.
  3. Return Result: The function returns the minimum of the two mismatch counts.

Time Complexity

The time complexity of this solution is O(n) where n is the length of the string. This is because we are making a single pass through the string to check each character against both patterns.

Space Complexity

The space complexity is O(1) as we are using a constant amount of extra space regardless of the input size.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI