# Replace All ?'s to Avoid Consecutive Repeating Characters **Difficulty:** EASY [External](https://leetcode.com/problems/replace-all-s-to-avoid-consecutive-repeating-characters) Canonical: https://scaleengineer.com/dsa/problems/replace-all-'s-to-avoid-consecutive-repeating-characters **Data structures:** String --- ## 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 <= 100` * `s` consist of lowercase English letters and `'?'`. # Approaches ## Greedy Iteration with Full Alphabet Scan 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. **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. **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 `'?'`. ### Explanation 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. ```java class Solution { public String modifyString(String s) { char[] chars = s.toCharArray(); int n = s.length(); for (int i = 0; i < n; i++) { if (chars[i] == '?') { for (char c = 'a'; c <= 'z'; c++) { boolean ok = true; if (i > 0 && chars[i - 1] == c) { ok = false; } if (i < n - 1 && chars[i + 1] == c) { ok = false; } if (ok) { chars[i] = c; break; } } } } return new String(chars); } } ``` ### 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. ## Optimized Greedy Iteration 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. **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. **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. ### Explanation 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. ```java class Solution { public String modifyString(String s) { char[] chars = s.toCharArray(); int n = s.length(); for (int i = 0; i < n; i++) { if (chars[i] == '?') { for (char c : new char[]{'a', 'b', 'c'}) { // Check left neighbor if (i > 0 && chars[i - 1] == c) { continue; } // Check right neighbor if (i < n - 1 && chars[i + 1] == c) { continue; } // Found a valid character chars[i] = c; break; } } } return new String(chars); } } ``` ### 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. # Solutions ### Java ```java class Solution { public String modifyString(String s) { char[] cs = s.toCharArray(); int n = cs.length; for (int i = 0; i < n; ++i) { if (cs[i] == '?') { for (char c = 'a'; c <= 'c'; ++c) { if ((i > 0 && cs[i - 1] == c) || (i + 1 < n && cs[i + 1] == c)) { continue; } cs[i] = c; break; } } } return String.valueOf(cs); } } ``` ### CPP ```cpp class Solution { public: string modifyString(string s) { int n = s.size(); for (int i = 0; i < n; ++i) { if (s[i] == '?') { for (char c : "abc") { if ((i && s[i - 1] == c) || (i + 1 < n && s[i + 1] == c)) { continue; } s[i] = c; break; } } } return s; } }; ``` ### Python ```python class Solution: 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) ```