Replace All ?'s to Avoid Consecutive Repeating Characters

Easy

#1450Time: O(N), where N is the length of the string. The outer loop runs N times. The inner loop runs at most 26 times (a constant) for each `'?'`. Therefore, the complexity is O(26 * N), which simplifies to O(N).Space: O(N), where N is the length of the string. This is required to store the character array, as strings are immutable in Java.

Data structures

String

Prompt

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 <= 100
s consist of lowercase English letters and '?'.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach iterates through the string and replaces each question mark ('?') with the first possible lowercase letter from the alphabet that doesn't create a sequence of consecutive repeating characters. It's a straightforward greedy algorithm.

Algorithm

Convert the input string s into a mutable character array chars.
Iterate through the chars array from left to right using an index i.
If the character at chars[i] is a '?':
- Start an inner loop, iterating through all 26 lowercase letters from 'a' to 'z' as candidate replacements.
- For each candidate character c, check if it is a valid replacement:
  - A replacement is valid if it is not equal to the left neighbor chars[i-1] (if i > 0).
  - And it is not equal to the right neighbor chars[i+1] (if i < s.length() - 1).
- If c is a valid replacement, update chars[i] to c and break the inner loop to move to the next position in the string.
After the main loop completes, convert the modified chars array back to a string and return it.

Walkthrough

The core idea is to process the string from left to right. Since the choice for a character at index i only depends on its immediate neighbors at i-1 and i+1, a greedy choice made at i will not invalidate future choices. We first convert the input string into a mutable data structure, like a character array, because strings are immutable in Java. We then loop through each character of the array. If we encounter a '?', we find a suitable replacement by iterating through all 26 lowercase letters from 'a' to 'z'. For each candidate letter, we check if it's different from the character to its left (if one exists) and the character to its right (if one exists). The first letter that satisfies these conditions is chosen as the replacement. Because there are 26 possible letters and at most two are forbidden (the left and right neighbors), we are guaranteed to find a valid replacement. Finally, we convert the modified character array back into a string.

1class Solution {2    public String modifyString(String s) {3        char[] chars = s.toCharArray();4        int n = s.length();5        for (int i = 0; i < n; i++) {6            if (chars[i] == '?') {7                for (char c = 'a'; c <= 'z'; c++) {8                    boolean ok = true;9                    if (i > 0 && chars[i - 1] == c) {10                        ok = false;11                    }12                    if (i < n - 1 && chars[i + 1] == c) {13                        ok = false;14                    }15                    if (ok) {16                        chars[i] = c;17                        break;18                    }19                }20            }21        }22        return new String(chars);23    }24}

Complexity

Time

O(N), where N is the length of the string. The outer loop runs N times. The inner loop runs at most 26 times (a constant) for each `'?'`. Therefore, the complexity is O(26 * N), which simplifies to O(N).

Space

O(N), where N is the length of the string. This is required to store the character array, as strings are immutable in Java.

Trade-offs

Pros

Simple to understand and implement.
Guaranteed to find a correct solution.

Cons

Slightly less performant than the optimized version due to potentially iterating through up to 26 characters for each '?'.

This is an optimized version of the greedy approach. Instead of checking the entire alphabet for a replacement, it leverages the fact that we only need to avoid at most two characters. Therefore, checking just three distinct characters (e.g., 'a', 'b', 'c') is sufficient to find a valid replacement.

Algorithm

Convert the input string s into a character array chars.
Loop through the array from i = 0 to s.length() - 1.
If chars[i] is equal to '?':
- Loop through a small, fixed set of candidate characters, for instance, {'a', 'b', 'c'}.
- For each candidate c, check if it's a valid replacement:
  - It must not be equal to chars[i-1] (if i > 0).
  - It must not be equal to chars[i+1] (if i < s.length() - 1).
- If c is valid, set chars[i] = c and break the inner loop.
After the main loop, create a new string from the chars array and return it.

Walkthrough

This approach follows the same greedy strategy of iterating from left to right. The key insight is that for any '?' at index i, we only need to find a character that is different from s[i-1] and s[i+1]. Since there are 26 lowercase letters available, and at most two are forbidden by the immediate neighbors, there are at least 24 valid choices. This means we don't need to scan the entire alphabet. By the pigeonhole principle, if we check any three distinct characters (for example, 'a', 'b', and 'c'), at least one of them must be a valid choice. The algorithm is nearly identical to the previous one, but the inner loop is replaced. Instead of looping 'a' through 'z', we just loop through 'a', 'b', and 'c'. This makes the check for each '?' a constant-time operation in practice.

1class Solution {2    public String modifyString(String s) {3        char[] chars = s.toCharArray();4        int n = s.length();5        for (int i = 0; i < n; i++) {6            if (chars[i] == '?') {7                for (char c : new char[]{'a', 'b', 'c'}) {8                    // Check left neighbor9                    if (i > 0 && chars[i - 1] == c) {10                        continue;11                    }12                    // Check right neighbor13                    if (i < n - 1 && chars[i + 1] == c) {14                        continue;15                    }16                    // Found a valid character17                    chars[i] = c;18                    break;19                }20            }21        }22        return new String(chars);23    }24}

Complexity

Time

O(N), where N is the length of the string. The outer loop runs N times, and the inner loop runs at most 3 times for each `'?'`. This is a true O(N) complexity with a minimal constant factor.

Space

O(N) to store the character array, which is necessary because strings in Java are immutable.

Trade-offs

Pros

Most efficient solution with a very small constant factor.
Simple logic and implementation.

Cons

There are no significant cons for this approach as it is optimal for the given problem constraints.

Solutions

Solution

1class Solution {2public3  String modifyString(String s) {4    char[] cs = s.toCharArray();5    int n = cs.length;6    for (int i = 0; i < n; ++i) {7      if (cs[i] == '?') {8        for (char c = 'a'; c <= 'c'; ++c) {9          if ((i > 0 && cs[i - 1] == c) || (i + 1 < n && cs[i + 1] == c)) {10            continue;11          }12          cs[i] = c;13          break;14        }15      }16    }17    return String.valueOf(cs);18  }19}

1class Solution {2public:3  string modifyString(string s) {4    int n = s.size();5    for (int i = 0; i < n; ++i) {6      if (s[i] == '?') {7        for (char c : "abc") {8          if ((i && s[i - 1] == c) || (i + 1 < n && s[i + 1] == c)) {9            continue;10          }11          s[i] = c;12          break;13        }14      }15    }16    return s;17  }18};

1class Solution:2    def modifyString(self, s: str) -> str: s = list(s) n = len(s) for i in range(n): if s[i] == "?": for c in "abc": if (i and s[i - 1] == c) or (i + 1 < n and s[i + 1] == c): continue s[i] = c break return "" . join(s)

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem