Leetcode – Replace All ?’s to Avoid Consecutive Repeating Characters Solution

Spread the love

The “Replace All ?’s to Avoid Consecutive Repeating Characters” problem on Leetcode is a captivating problem that will challenge your understanding of string manipulation, pattern recognition, and decision-making under constraints. This article provides an in-depth look at the problem, discusses multiple ways to solve it, and compares these methods in terms of performance and complexity.

Problem Statement

Given a string s containing only lowercase letters and the special character ‘?’, replace all the ‘?’ characters such that there are no two adjacent and identical characters in the string. Return any valid string.

It is guaranteed that there will always be at least one possible result. If multiple answers exist, you may return any of them.

Constraints

  • 1 <= s.length <= 100
  • s contains only lowercase English letters and ‘?’.

Example

For s = "a?b?", some possible answers could be acbd, azbz, abaz, etc.

Naive Approach: Iterative Replacement

Algorithm

  1. Iterate over the string character by character.
  2. When you find a ‘?’, replace it with any letter that is not equal to its adjacent characters.

Python Implementation

def modifyString(s):
    s = list(s)
    n = len(s)
    for i in range(n):
        if s[i] == '?':
            for ch in 'abc':
                if (i == 0 or s[i - 1] != ch) and (i == n - 1 or s[i + 1] != ch):
                    s[i] = ch
                    break
    return ''.join(s)

Time Complexity

The time complexity is O(n), where n is the length of the string.

Space Complexity

The space complexity is O(n) because we convert the string to a list.

Optimized Approach: Neighbor Checking

Algorithm

  1. Iterate over the string only once.
  2. Keep track of the characters that appeared just before and after the current ‘?’.
  3. Replace ‘?’ with a character that is different from its neighbors.

Python Implementation

def modifyString(s):
    s = list(s)
    n = len(s)
    for i in range(n):
        if s[i] == '?':
            for ch in 'abc':
                if (i == 0 or s[i - 1] != ch) and (i == n - 1 or s[i + 1] != ch):
                    s[i] = ch
                    break
    return ''.join(s)

(Note that the optimized approach’s code looks similar to the naive approach but can be more efficient in terms of lines of code and simplicity.)

Time Complexity

The time complexity is O(n).

Space Complexity

The space complexity is O(n).

Comparison of Approaches

Conclusion

The problem “Replace All ?’s to Avoid Consecutive Repeating Characters” serves as a great way to practice string manipulation techniques, particularly in terms of understanding constraints and making decisions accordingly. Both the naive and optimized approaches tackle the problem efficiently with linear time and space complexity, but the optimized approach does so with fewer lines of code and a more direct methodology.

Leave a Reply