Replace All ?'s to Avoid Consecutive Repeating Characters - Solution & Explanation
Problem Statement
Given a string s containing only lowercase English letters and the '?' character, convert all the '?' characters into lowercase letters such that the final string does not contain any consecutive repeating characters. You cannot modify the non '?' characters.
It is guaranteed that there are no consecutive repeating characters in the given string except for '?'.
Return the final string after all the conversions (possibly zero) have been made. If there is more than one solution, return any of them. It can be shown that an answer is always possible with the given constraints.
Example 1:
Input: s = "?zs" Output: "azs" Explanation: There are 25 solutions for this problem. From "azs" to "yzs", all are valid. Only "z" is an invalid modification as the string will consist of consecutive repeating characters in "zzs".
Example 2:
Input: s = "ubv?w" Output: "ubvaw" Explanation: There are 24 solutions for this problem. Only "v" and "w" are invalid modifications as the strings will consist of consecutive repeating characters in "ubvvw" and "ubvww".
Constraints:
1 <= s.length <= 100sconsist of lowercase English letters and'?'.
Approach Overview
Problem Overview: You receive a string containing lowercase letters and the character ?. Each ? must be replaced with a lowercase letter so that no two adjacent characters are the same. The final string must preserve the existing characters while ensuring every neighbor pair differs.
Approach 1: Left to Right Replacement (O(n) time, O(1) space)
Scan the string from left to right and immediately resolve every ?. For each position, try a small set of candidate letters (typically 'a', 'b', 'c') and choose one that differs from both the previous character and the next character if it already exists. Because only adjacent conflicts matter, checking two neighbors is enough. This greedy strategy works since the alphabet gives enough choices to avoid collisions while keeping the replacement local.
Implementation converts the string to a mutable array, iterates once, and performs constant-time neighbor checks for every ?. The approach runs in O(n) time with O(1) extra space since only a few temporary characters are tested. This pattern appears frequently in string manipulation problems where constraints depend only on adjacent elements.
Approach 2: Two-pointer Method (O(n) time, O(1) space)
The two-pointer variant handles segments of consecutive ?. One pointer marks the start of a block of unknown characters while another scans forward until the block ends. After identifying the segment, fill characters sequentially while ensuring the first replacement differs from the left boundary and the last replacement differs from the right boundary.
Inside the segment, alternate safe characters so no internal duplicates appear. This method explicitly treats ??? sequences as small subproblems and resolves them while respecting boundary characters. Time complexity remains O(n) because each index is processed once, and the algorithm uses O(1) space.
Problems like this highlight greedy reasoning in string processing and often appear alongside patterns from two pointers or simple greedy decisions where only local constraints matter.
Recommended for interviews: The left-to-right greedy replacement is the expected solution. It is simpler, runs in linear time, and demonstrates that you recognized only adjacent comparisons matter. Mentioning the segment-based or two-pointer variation shows deeper reasoning, but the single-pass greedy implementation is usually what interviewers expect.
Approach 1: Left to Right Replacement
This approach involves iterating over the string from left to right and replacing each '?' with a suitable character that does not create consecutive duplicates.
The Python solution iterates through each character of the string. When it encounters a '?', it tries replacing it with 'a', 'b', or 'c'. The chosen character is skipped if it creates consecutive identical characters. The process continues until all '?' are replaced.
Complexity
Time Complexity: O(n), where n is the length of the string, as we iterate through it only once.
Space Complexity: O(n), due to the list conversion of the string for mutable operations.
Approach 2: Two-pointer Method
This method uses two pointers to traverse the string and replace '?' characters while ensuring no consecutive characters are identical by checking with the alternate pointer.
In this Python solution, a while loop and pointers manage character replacement. The key advantage here is handling previous and next character checks in conjunction.
Complexity
Time Complexity: O(n), where n is the input length.
Space Complexity: O(n) with mutable list handling.
Approach 3: Default Approach
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Left to Right Replacement | Time Complexity: O(n), where n is the length of the string, as we iterate through it only once. |
| Two-pointer Method | Time Complexity: O(n), where n is the input length. |
| Default Approach | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Left to Right Replacement | O(n) | O(1) | Best general solution. Simple greedy scan replacing '?' while checking neighbors. |
| Two-pointer Method | O(n) | O(1) | Useful when handling blocks of consecutive '?' and reasoning about boundaries. |
Video Solution
LeetCode 1576. Replace All ?'s to Avoid Consecutive Repeating Characters - Interview Prep Ep 97 • Fisher Coder • 2,384 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Replace All ?'s to Avoid Consecutive Repeating Characters easy or hard?
Replace All ?'s to Avoid Consecutive Repeating Characters Python/Java solution
How to solve Replace All ?'s to Avoid Consecutive Repeating Characters in O(n)?
What is the best approach for Replace All ?'s to Avoid Consecutive Repeating Characters?
Is Replace All ?'s to Avoid Consecutive Repeating Characters asked at Google/Amazon/Meta?
What data structure is used in Replace All ?'s to Avoid Consecutive Repeating Characters?
What is the time complexity of Replace All ?'s to Avoid Consecutive Repeating Characters?
Ready to solve this problem?
Practice Replace All ?'s to Avoid Consecutive Repeating Characters with our built-in code editor and test cases.
Practice on FleetCode