algoadvance

Leetcode 1576. Replace All ?’s to Avoid Consecutive Repeating Characters

Problem Statement

You are given a string s that contains only lowercase English letters and '?' characters. You need to replace all '?' characters in the string such that no two adjacent characters are the same. There may be multiple valid solutions, return any one of them.

Clarifying Questions

  1. Can the input string be empty?
    • Yes, if the input string is empty, we should return an empty string.
  2. Can the string contain only ? characters?
    • Yes, and we need to replace them with valid characters.
  3. What is the maximum length of the string?
    • Length constraints are typical for LeetCode problems, usually up to 10^4 characters.

Strategy

  1. Iterate through the string and check each character.
  2. If a character is '?', replace it with a character that doesn’t match the previous or next character to avoid consecutive repeating characters.
  3. Use characters like ‘a’, ‘b’, and ‘c’ to ensure there are no consecutive duplicates since there are plenty of choices among lowercase English letters.

Code

#include <iostream>
#include <string>

std::string modifyString(std::string s) {
    int n = s.length();
    
    for (int i = 0; i < n; i++) {
        if (s[i] == '?') {
            for (char ch = 'a'; ch <= 'c'; ch++) {
                if ((i > 0 && s[i-1] == ch) || (i < n - 1 && s[i+1] == ch)) {
                    continue;
                } else {
                    s[i] = ch;
                    break;
                }
            }
        }
    }
    
    return s;
}

int main() {
    std::string s = "?zs";
    std::cout << "Modified string: " << modifyString(s) << std::endl;
    return 0;
}

Explanation

  1. Loop through each character in the input string s.
  2. If we encounter a '?', we attempt to replace it with characters ‘a’, ‘b’, or ‘c’.
  3. For each of these characters, check if it matches the previous character (s[i-1]) or the next character (s[i+1]). If it does not, we replace the '?' with this character.
  4. This ensures that no two adjacent characters will be the same after the replacement.

Time Complexity

This algorithm should efficiently replace all occurrences of '?' with characters that ensure no consecutive characters are the same.

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