LeetCode 1576 - Replace All ?'s to Avoid Consecutive Repeating Characters
This problem asks us to take a string s consisting of lowercase English letters and the character '?' and replace every '?' with a lowercase letter so that no two consecutive characters in the resulting string are the same.
Difficulty: 🟢 Easy
Topics: String
Solution
Problem Understanding
This problem asks us to take a string s consisting of lowercase English letters and the character '?' and replace every '?' with a lowercase letter so that no two consecutive characters in the resulting string are the same. Importantly, we are not allowed to change any existing letters in the string.
The input string can be of length from 1 to 100, which is relatively small. This means we can use a straightforward linear solution without worrying about performance issues. The problem guarantees that the input string does not have consecutive repeating letters except possibly '?', so we do not need to handle invalid input strings. Also, it guarantees that a valid replacement is always possible, so we do not have to return a failure case.
Key edge cases include strings that are entirely '?', strings that start or end with '?', and strings where '?' is surrounded by identical letters on both sides, for example "a?b" or "a?aa".
Approaches
The naive or brute-force approach would be to try every possible lowercase letter replacement for each '?' in the string, recursively generating all possible strings and checking for consecutive duplicates. While this works in theory, it is extremely inefficient, with a time complexity of $O(26^k)$ where $k$ is the number of '?' characters. This grows exponentially, so even a small number of '?' could make the brute-force approach infeasible.
The optimal approach leverages the observation that we do not need to try all letters. For each '?', we can choose a letter that is different from its previous and next characters. Since there are 26 letters and we only need to avoid at most two letters (the previous and the next), there is always a valid choice. This leads to a simple linear scan through the string, replacing '?' greedily while ensuring no consecutive duplicates are created.
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(26^k) | O(n) | Tries all possible replacements recursively, inefficient for multiple '?' |
| Optimal | O(n) | O(n) | Linear scan, replaces '?' greedily, always finds a valid solution |
Algorithm Walkthrough
- Convert the input string into a mutable list of characters. Strings in Python and Go are immutable, so we need a list or slice for in-place modifications.
- Iterate over each character in the string from left to right.
- Whenever a
'?'is encountered, determine the valid letters by checking the previous character (if any) and the next character (if any). We must avoid using these letters to prevent consecutive duplicates. - Pick any letter from the remaining valid options. A simple approach is to iterate from
'a'to'z'and take the first letter that is allowed. - Replace
'?'with the chosen letter. - After processing all characters, join the list back into a string and return it.
Why it works: At each step, we ensure that the chosen replacement is different from the adjacent characters. Since there are 26 letters, avoiding two specific letters will always leave at least 24 options, guaranteeing a valid replacement. This greedy choice produces a correct final string.
Python Solution
class Solution:
def modifyString(self, s: str) -> str:
s_list = list(s)
n = len(s_list)
for i in range(n):
if s_list[i] == '?':
for c in 'abcdefghijklmnopqrstuvwxyz':
prev_char = s_list[i - 1] if i > 0 else None
next_char = s_list[i + 1] if i < n - 1 else None
if c != prev_char and c != next_char:
s_list[i] = c
break
return ''.join(s_list)
The implementation converts the string to a list for mutability, scans from left to right, and replaces '?' greedily. The prev_char and next_char checks guarantee no consecutive duplicates are created. After the loop, the list is joined back into a string.
Go Solution
func modifyString(s string) string {
n := len(s)
sList := []byte(s)
for i := 0; i < n; i++ {
if sList[i] == '?' {
for c := byte('a'); c <= 'z'; c++ {
var prevChar, nextChar byte
if i > 0 {
prevChar = sList[i-1]
}
if i < n-1 {
nextChar = sList[i+1]
}
if c != prevChar && c != nextChar {
sList[i] = c
break
}
}
}
}
return string(sList)
}
In Go, we convert the string to a []byte for mutability. The logic is identical to the Python version, with type differences and zero-value handling for prevChar and nextChar.
Worked Examples
Example 1: "?zs"
| Index | Character | Prev | Next | Replacement |
|---|---|---|---|---|
| 0 | ? | None | z | a |
| 1 | z | a | s | z (unchanged) |
| 2 | s | z | None | s (unchanged) |
Result: "azs"
Example 2: "ubv?w"
| Index | Character | Prev | Next | Replacement |
|---|---|---|---|---|
| 0 | u | None | b | u (unchanged) |
| 1 | b | u | v | b (unchanged) |
| 2 | v | b | ? | v (unchanged) |
| 3 | ? | v | w | a |
| 4 | w | a | None | w (unchanged) |
Result: "ubvaw"
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(n) | Each character is scanned once, and for '?' we try at most 26 letters. |
| Space | O(n) | We store a mutable list/slice of size n. |
The algorithm runs efficiently due to the small string size and the greedy selection of replacement letters.
Test Cases
# Provided examples
assert Solution().modifyString("?zs") == "azs" # '?' at start
assert Solution().modifyString("ubv?w") == "ubvaw" # '?' in middle
# Edge cases
assert Solution().modifyString("?") in "abcdefghijklmnopqrstuvwxyz" # single '?'
assert Solution().modifyString("a?") != "aa" # avoids repeat at end
assert Solution().modifyString("?a") != "aa" # avoids repeat at start
assert Solution().modifyString("???") # multiple '?'
assert Solution().modifyString("a?b?c?") # alternating '?'s
# No '?' input
assert Solution().modifyString("abc") == "abc" # unchanged string
| Test | Why |
|---|---|
| "?zs" | '?' at start handled correctly |
| "ubv?w" | '?' in middle handled correctly |
| "?" | single '?' edge case |
| "a?" | '?' at end avoids consecutive duplicates |
| "?a" | '?' at start avoids consecutive duplicates |
| "???" | multiple consecutive '?' handled greedily |
| "abc" | no '?' input returns unchanged string |
Edge Cases
One important edge case is a string composed entirely of '?', like "???". The algorithm handles this by replacing each '?' sequentially with a letter that does not repeat the previous one. Since the first character has no previous, any letter is valid.
Another edge case is when '?' appears at the start or end of the string. For example, "?a" or "a?". In both cases, the algorithm checks for previous or next characters and avoids them during replacement, ensuring no consecutive duplicates.
A third edge case is consecutive '?' characters, like "a??b". The algorithm replaces them one by one from left to right, always considering the previous character (just replaced) and the next character (fixed or '?'). This ensures the replacements never conflict and no consecutive duplicates arise.