Replace All ?'s to Avoid Consecutive Repeating Characters solution and explanation
9 more videos on this problem
LeetCode 1576. Replace All ?'s to Avoid Consecutive Repeating Characters - Interview Prep Ep 97Fisher Coder · 8:15 · 2K views
1576. Replace All ?'s to Avoid Consecutive Repeating Characters | LeetCode Weekly Contest 205CP Addict · 4:53 · 600 views
Replace all ?‘s to avoid consecutive repeating charactersAutomationDigest · 8:51 · 490 views
1576. Replace All ?'s to Avoid Consecutive Repeating Characters (Leetcode Easy)Programming Live with Larry · 7:45 · 479 views
Weekly Contest 205 || Problem 1576 , 1577 , 1578 || LEETCODEcode Explainer · 18:50 · 358 views
1576. Replace All ?'s to Avoid Consecutive Repeating Characters | Weekly Contest 205Coding Gist · 3:07 · 172 views
1576 Replace All 's to Avoid Consecutive Repeating CharactersMath Geeks · 3:23 · 147 views
Replace All ?'s to Avoid Consecutive Repeating Characters | Leetcode #1576 #golangYoussef Azrak · 11:07 · 129 views
Leetcode 1576 Replace All 's to Avoid Consecutive Repeating CharactersAlgorithmicIQ · 18:16 · 23 views
LeetCode Problem Solution | Replace All ?'s Character To Avoid Consecutive Repeating | Fox-TechFox-Tech Academy · 20:22 · 295 views
The problem
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.
def replace_question_marks(s):
s = list(s)
for i in range(len(s)):
if s[i] == '?':
for c in 'abc':
if (i > 0 and s[i - 1] == c) or (i < len(s) - 1 and s[i + 1] == c):
continue
s[i] = c
break
return ''.join(s)public class Solution {
public String replaceQuestionMarks(String s) {
char[] str = s.toCharArray();
for (int i = 0; i < str.length; i++) {
if (str[i] == '?') {
for (char c = 'a'; c <= 'c'; c++) {
if ((i > 0 && str[i - 1] == c) || (i < str.length - 1 && str[i + 1] == c))
continue;
str[i] = c;
break;
}
}
}
return new String(str);
}
}#include <string>
#include <iostream>
using namespace std;
string replaceQuestionMarks(string s) {
for (int i = 0; i < s.size(); ++i) {
if (s[i] == '?') {
for (char c = 'a'; c <= 'c'; ++c) {
if ((i > 0 && s[i-1] == c) || (i < s.size() - 1 && s[i+1] == c))
continue;
s[i] = c;
break;
}
}
}
return s;
}function replaceQuestionMarks(s) {
let arr = s.split('');
for (let i = 0; i < arr.length; i++) {
if (arr[i] === '?') {
for (let c of ['a', 'b', 'c']) {
if ((i > 0 && arr[i - 1] === c) || (i < arr.length - 1 && arr[i + 1] === c))
continue;
arr[i] = c;
break;
}
}
}
return arr.join('');
}#include <stdio.h>
#include <string.h>
void replaceQuestionMarks(char *s) {
int len = strlen(s);
for (int i = 0; i < len; ++i) {
if (s[i] == '?') {
for (char c = 'a'; c <= 'c'; ++c) {
if ((i > 0 && s[i - 1] == c) || (i < len - 1 && s[i + 1] == c))
continue;
s[i] = c;
break;
}
}
}
printf("%s", s);
}public class Solution {
public string ReplaceQuestionMarks(string s) {
char[] arr = s.ToCharArray();
for (int i = 0; i < arr.Length; i++) {
if (arr[i] == '?') {
for (char c = 'a'; c <= 'c'; c++) {
if ((i > 0 && arr[i - 1] == c) || (i < arr.Length - 1 && arr[i + 1] == c))
continue;
arr[i] = c;
break;
}
}
}
return new string(arr);
}
}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.
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.
def replace_question_marks_2(s):
s = list(s)
n = len(s)
i = 0
while i < n:
if s[i] == '?':
prev = s[i-1] if i > 0 else ''
next = s[i+1] if i < n-1 else ''
for c in 'abc':
if c != prev and c != next:
s[i] = c
break
i += 1
return ''.join(s)public class Solution {
public String replaceQuestionMarks_2(String s) {
char[] str = s.toCharArray();
int n = str.length;
for (int i = 0; i < n; i++) {
if (str[i] == '?') {
char prev = (i > 0) ? str[i-1] : ' ';
char next = (i < n - 1) ? str[i+1] : ' ';
for (char c = 'a'; c <= 'c'; c++) {
if (c != prev && c != next) {
str[i] = c;
break;
}
}
}
}
return new String(str);
}
}#include <string>
#include <iostream>
using namespace std;
string replaceQuestionMarks_2(string s) {
int n = s.size();
for (int i = 0; i < n; ++i) {
if (s[i] == '?') {
char prev = (i > 0) ? s[i-1] : ' ';
char next = (i < n - 1) ? s[i+1] : ' ';
for (char c = 'a'; c <= 'c'; ++c) {
if (c != prev && c != next) {
s[i] = c;
break;
}
}
}
}
return s;
}function replaceQuestionMarks_2(s) {
let n = s.length;
let arr = s.split('');
for (let i = 0; i < n; i++) {
if (arr[i] === '?') {
let prev = (i > 0) ? arr[i - 1] : '';
let next = (i < n - 1) ? arr[i + 1] : '';
for (let c of ['a', 'b', 'c']) {
if (c !== prev && c !== next) {
arr[i] = c;
break;
}
}
}
}
return arr.join('');
}#include <stdio.h>
#include <string.h>
void replaceQuestionMarks_2(char *s) {
int n = strlen(s);
for (int i = 0; i < n; ++i) {
if (s[i] == '?') {
char prev = (i > 0) ? s[i-1] : ' ';
char next = (i < n-1) ? s[i+1] : ' ';
for (char c = 'a'; c <= 'c'; ++c) {
if (c != prev && c != next) {
s[i] = c;
break;
}
}
}
}
printf("%s", s);
}public class Solution {
public string ReplaceQuestionMarks_2(string s) {
char[] arr = s.ToCharArray();
int n = arr.Length;
for (int i = 0; i < n; i++) {
if (arr[i] == '?') {
char prev = (i > 0) ? arr[i - 1] : ' ';
char next = (i < n - 1) ? arr[i + 1] : ' ';
for (char c = 'a'; c <= 'c'; c++) {
if (c != prev && c != next) {
arr[i] = c;
break;
}
}
}
}
return new string(arr);
}
}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.
Time Complexity: O(n), where n is the input length.
Space Complexity: O(n) with mutable list handling.
Approach 3: Default Approach
function modifyString(s: string): string {
const cs = s.split('');
const n = s.length;
for (let i = 0; i < n; ++i) {
if (cs[i] === '?') {
for (const c of 'abc') {
if ((i > 0 && cs[i - 1] === c) || (i + 1 < n && cs[i + 1] === c)) {
continue;
}
cs[i] = c;
break;
}
}
}
return cs.join('');
}func modifyString(s string) string {
n := len(s)
cs := []byte(s)
for i := range s {
if cs[i] == '?' {
for c := byte('a'); c <= byte('c'); c++ {
if (i > 0 && cs[i-1] == c) || (i+1 < n && cs[i+1] == c) {
continue
}
cs[i] = c
break
}
}
}
return string(cs)
}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 | – |
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. |
Frequently asked questions
Is Replace All ?'s to Avoid Consecutive Repeating Characters easy or hard?
LeetCode classifies this problem as Easy. The challenge is recognizing that only adjacent characters matter and that a small fixed set of letters can always avoid conflicts, enabling a straightforward greedy solution.
Replace All ?'s to Avoid Consecutive Repeating Characters Python/Java solution
Both Python and Java implementations follow the same greedy pattern. Convert the string to a list or char array, iterate through it, and replace '?' with a character different from adjacent positions. The logic stays O(n) time and O(1) extra space across Python, Java, C++, and JavaScript.
How to solve Replace All ?'s to Avoid Consecutive Repeating Characters in O(n)?
Convert the string to a mutable array and scan from left to right. When encountering '?', test characters like 'a', 'b', or 'c' and choose one that differs from the previous character and the next character if it already exists. Because only adjacent equality matters, this local greedy choice guarantees a valid result in a single pass.
What is the best approach for Replace All ?'s to Avoid Consecutive Repeating Characters?
The greedy left-to-right replacement approach is the most efficient. Iterate through the string and whenever you encounter '?', replace it with a character that differs from both its previous and next neighbors. Only a few candidate letters (such as 'a', 'b', 'c') are needed, making the algorithm O(n) time and O(1) space.
Is Replace All ?'s to Avoid Consecutive Repeating Characters asked at Google/Amazon/Meta?
Variants of this problem appear in interviews focusing on string manipulation and greedy reasoning. Large companies such as Google, Amazon, and Meta often ask similar problems where characters must be replaced while respecting adjacency constraints or avoiding duplicates.
What data structure is used in Replace All ?'s to Avoid Consecutive Repeating Characters?
The problem mainly uses a character array or mutable string structure so characters can be replaced in place. The algorithm relies on simple index access and neighbor comparison rather than advanced data structures.
What is the time complexity of Replace All ?'s to Avoid Consecutive Repeating Characters?
The optimal solution runs in O(n) time where n is the length of the string. Each character is processed once and each '?' replacement checks only adjacent characters. Space complexity is O(1) since only a few temporary variables are used.