Replace All ?'s to Avoid Consecutive Repeating Characters Solution

In this page, we will solve the Replace All ?'s to Avoid Consecutive Repeating Characters problem using multiple approaches: greedy and character replacement. We will provide the implementation of the solution in Python, JavaScript, TypeScript, Java, and C++.

Problem Description

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.

Return the final string after replacing all the '?' characters.

It is guaranteed that there are no consecutive repeating characters in the given string except for '?'.

A string a is considered lexicographically smaller than a string b if in the first position where a and b differ, string a has a character strictly smaller than the corresponding character in b. For example, "abcc" is lexicographically smaller than "abcd" because the first position they differ is at the fourth character, and 'c' is smaller than 'd'.

Examples

Example 1:

Input: s = "?zs"
Output: "azs"
Explanation: There are 25 possible characters for each position. The first position is '?', so we replace it with 'a'. The second position is 'z', so we keep it as is. The third position is 's', so we keep it as is.

Example 2:

Input: s = "ubv?w"
Output: "ubvaw"
Explanation: The first position is 'u', so we keep it as is. The second position is 'b', so we keep it as is. The third position is 'v', so we keep it as is. The fourth position is '?', so we replace it with 'a'. The fifth position is 'w', so we keep it as is.

Example 3:

Input: s = "j?qg??b"
Output: "jaqgacb"

Example 4:

Input: s = "??yw?ipkj?"
Output: "abywaipkja"

Constraints

• $1 <= s.length <= 100$
• s consists only of lowercase English letters and the '?' character.

---

Solution for Replace All ?'s to Avoid Consecutive Repeating Characters

Intuition and Approach

The problem can be solved using different approaches. We will start with a greedy approach and then look at a character replacement approach.

• Greedy
• Character Replacement

Approach 1: Greedy

We iterate through the string and whenever we encounter a '?', we replace it with the smallest character that is different from its neighboring characters.

Implementation

Live Editor

function modifyString() {
  const s = "?zs";

  const modifyString = function(s) {
    s = s.split('');
    const n = s.length;
    for (let i = 0; i < n; i++) {
      if (s[i] === '?') {
        let prev = i === 0 ? null : s[i - 1];
        let next = i === n - 1 ? null : s[i + 1];
        let candidate = 'a';
        while (candidate === prev || candidate === next) {
          candidate = String.fromCharCode(candidate.charCodeAt(0) + 1);
        }
        s[i] = candidate;
      }
    }
    return s.join('');
  };

  const result = modifyString(s);
  return (
    <div>
      <p>
        <b>Input:</b> s = {JSON.stringify(s)}
      </p>
      <p>
        <b>Output:</b> {result}
      </p>
    </div>
  );
}

Result

Loading...

Codes in Different Languages

JavaScript

Written by @manishh12

 function modifyString(s) {
   s = s.split('');
   const n = s.length;
   for (let i = 0; i < n; i++) {
     if (s[i] === '?') {
       let prev = i === 0 ? null : s[i - 1];
       let next = i === n - 1 ? null : s[i + 1];
       let candidate = 'a';
       while (candidate === prev || candidate === next) {
         candidate = String.fromCharCode(candidate.charCodeAt(0) + 1);
       }
       s[i] = candidate;
     }
   }
   return s.join('');
 }

TypeScript

Written by @manishh12

 function modifyString(s: string): string {
   s = s.split('');
   const n = s.length;
   for (let i = 0; i < n; i++) {
     if (s[i] === '?') {
       let prev = i === 0 ? null : s[i - 1];
       let next = i === n - 1 ? null : s[i + 1];
       let candidate = 'a';
       while (candidate === prev || candidate === next) {
         candidate = String.fromCharCode(candidate.charCodeAt(0) + 1);
       }
       s[i] = candidate;
     }
   }
   return s.join('');
 }

Python

Written by @manishh12

 class Solution:
     def modifyString(self, s: str) -> str:
         s = list(s)
         n = len(s)
         for i in range(n):
             if s[i] == '?':
                 prev = s[i - 1] if i > 0 else None
                 next = s[i + 1] if i < n - 1 else None
                 candidate = 'a'
                 while candidate == prev or candidate == next:
                     candidate = chr(ord(candidate) + 1)
                 s[i] = candidate
         return ''.join(s)

Java

Written by @manishh12

 class Solution {
     public String modifyString(String s) {
         char[] chars = s.toCharArray();
         int n = chars.length;
         for (int i = 0; i < n; i++) {
             if (chars[i] == '?') {
                 char prev = i == 0 ? 0 : chars[i - 1];
                 char next =

i == n - 1 ? 0 : chars[i + 1];
                 char candidate = 'a';
                 while (candidate == prev || candidate == next) {
                     candidate++;
                 }
                 chars[i] = candidate;
             }
         }
         return new String(chars);
     }
 }

C++

Written by @manishh12

 class Solution {
 public:
     string modifyString(string s) {
         for (int i = 0; i < s.length(); ++i) {
             if (s[i] == '?') {
                 char prev = i == 0 ? 0 : s[i - 1];
                 char next = i == s.length() - 1 ? 0 : s[i + 1];
                 char candidate = 'a';
                 while (candidate == prev || candidate == next) {
                     candidate++;
                 }
                 s[i] = candidate;
             }
         }
         return s;
     }
 };

Complexity Analysis

• Time Complexity: $O(n)$
• Space Complexity: $O(n)$
• Where n is the length of the string s.
• The time complexity is linear because we iterate through the string only once.
• The space complexity is also linear because we use an array to store the modified string.

Note

By using these approaches, we can efficiently solve the Replace All ?'s to Avoid Consecutive Repeating Characters problem for the given constraints.

References

• LeetCode Problem: LeetCode Problem
• Solution Link: Replace All ?'s to Avoid Consecutive Repeating Characters Solution on LeetCode
• Authors LeetCode Profile: Manish Kumar Gupta