1576. Replace All 's to Avoid Consecutive Repeating Characters

EasyString
Leetcode Link

Problem Description

The problem asks us to take a string that contains only lowercase English letters and the '?' character. Our goal is to replace every '?' in the string with a lowercase English letter such that no two consecutive characters in the final string are identical. Note that the provided string does not have consecutive repeating characters other than '?'. The challenge is to do this replacement in such a way that we never end up with two of the same characters next to each other. Additionally, we are not allowed to change any characters other than '?'. The requirement is to create a valid string that adheres to these constraints, and we can return any valid answer since there may be multiple solutions.

Intuition

To solve this problem, we need to generate a string with no two identical consecutive characters by replacing '?' with lowercase English letters. The intuition behind the approach is relatively straightforward.

  1. We iterate through the string to find the '?' characters that need replacement.
  2. For each '?' character found, we attempt to replace it with a character from a set of possible options (in this case, 'a', 'b', or 'c').
  3. We choose a replacement character that is different from the characters immediately before and after the current '?' to ensure there are no consecutive repeating characters.
  4. This is managed by checking the adjacent characters of each '?' position before deciding which character to assign to it.
  5. Since the string is guaranteed not to have consecutive repeating characters apart from '?', and we're using three different characters for replacement, there is always at least one character that will not form a repeating sequence.

This strategy leverages the fact that only three different characters are needed to ensure that we can replace any '?' without forming a consecutive repeating pair, since the English alphabet has more than two characters.

Solution Approach

To implement the solution, we convert the input string s into a list, making it mutable so we can easily replace '?' characters in place. Then, we go through the following steps:

  1. Loop through each character in the list by its index. We only need to take action when we encounter a '?' character.

  2. When a '?' is found, we must find a replacement character that doesn't match the character before or after the current position. Since we're only dealing with lowercase English letters, we use a small set of options 'a', 'b', and 'c' to find a suitable replacement. This small subset is sufficient because we're guaranteed there are no consecutive repeating characters except for '?'.

  3. For each candidate replacement character c, we perform a check:

    • If the '?' is not the first character in the list (i.e., i > 0), we need to ensure the previous character s[i - 1] is not the same as our candidate c.
    • If the '?' is not the last character in the list (i.e., i + 1 < n), we need to make sure the next character s[i + 1] is not the same as our candidate c.
  4. If both conditions are satisfied (meaning c does not match neighboring characters), we set s[i] to c and break out of the inner loop, as our replacement is done for this position.

  5. After handling all '?' characters, we join the list back into a string with "".join(s) and return the result.

The key data structure used in the solution is a list, which allows us to replace characters in the string easily. The algorithm iterates through the characters of the string once, making the time complexity O(n), where n is the length of the string. We employ a simple replacement strategy that checks adjacent characters to ensure we meet the problem's conditions.

Here is the Python code for the implementation:

1class Solution:
2    def modifyString(self, s: str) -> str:
3        s = list(s)
4        n = len(s)
5        for i in range(n):
6            if s[i] == "?":
7                for c in "abc":
8                    if (i and s[i - 1] == c) or (i + 1 < n and s[i + 1] == c):
9                        continue
10                    s[i] = c
11                    break
12        return "".join(s)

This solution efficiently ensures that the resulting string will have no consecutive repeating characters, utilizing minimal checks and avoiding unnecessary complexity.

Example Walkthrough

Let's walk through a small example to illustrate the solution approach using the given Python code.

Suppose we have the input string s = "ab??ac?". We are tasked to replace the '?' characters such that no two consecutive characters are identical.

Following the steps of the solution:

  1. We first convert s to a list: ['a', 'b', '?', '?', 'a', 'c', '?'].

  2. Then we loop through each character:

    • For the first two characters 'a' and 'b', no action is taken since they are not '?'.
    • At index 2 and 3, we find two '?' characters that need to be replaced.
  3. For the first '?', at index 2, we need to choose a character that is not 'b' (preceding character) and not 'a' (the next character which is currently '?', but we assume it might turn into 'a' since 'a' is the character following the next '?'). The candidate replacement character can be 'c'.

  4. We now replace the first '?', and our string list becomes ['a', 'b', 'c', '?', 'a', 'c', '?'].

  5. For the second '?', at index 3, we need a character that is not 'c' (preceding character) and not 'a' (following character). The candidate replacement character can be 'b'.

  6. We replace the second '?', and our list now looks like ['a', 'b', 'c', 'b', 'a', 'c', '?'].

  7. At the last '?', index 6, we choose a character that is not 'c' (preceding character). We can pick either 'a' or 'b' (since there is no following character), let's pick 'a'.

  8. After replacing the last '?', our final list is ['a', 'b', 'c', 'b', 'a', 'c', 'a'].

  9. We join this list to form the final string, which is "abcba" + "ca" = "abcbaca".

The output string is valid as there are no two consecutive, identical characters. This example demonstrates one of the many possible valid strings that can be formed following the outlined approach.

Python Solution

1class Solution:
2    def modifyString(self, s: str) -> str:
3        # Convert the input string into a list to modify characters
4        char_list = list(s)
5        n = len(char_list)
6
7        # Loop through each character in the list
8        for i in range(n):
9            # Check for '?' placeholders needing replacement
10            if char_list[i] == "?":
11                # Try replacing with characters 'a', 'b', or 'c'
12                for c in "abc":
13                    # Ensure the replacement doesn't match neighboring characters
14                    if (i > 0 and char_list[i - 1] == c) or (i + 1 < n and char_list[i + 1] == c):
15                        continue
16                    # Once a valid character is found, replace '?' and move to the next character
17                    char_list[i] = c
18                    break
19      
20        # Join the list back into a string and return
21        return "".join(char_list)
22

Java Solution

1class Solution {
2    public String modifyString(String s) {
3        // Convert the string to a char array to modify characters in place.
4        char[] charArray = s.toCharArray();
5        int length = charArray.length;
6
7        // Iterate over each character in the char array.
8        for (int i = 0; i < length; ++i) {
9            // Check if the current character is a question mark.
10            if (charArray[i] == '?') {
11                // Try replacing '?' with 'a', 'b', or 'c'.
12                for (char c = 'a'; c <= 'c'; ++c) {
13                    // Check if the same character is present on the left or right.
14                    // Make sure not to go out of bounds by checking the index.
15                    if ((i > 0 && charArray[i - 1] == c) || (i + 1 < length && charArray[i + 1] == c)) {
16                        // If the same character is on either side, continue to the next character.
17                        continue;
18                    }
19                    // Assign the character that doesn't match its neighbors.
20                    charArray[i] = c;
21                    // Once we have found a suitable character, break the inner loop.
22                    break;
23                }
24            }
25        }
26        // Convert the char array back to a string and return it.
27        return String.valueOf(charArray);
28    }
29}
30

C++ Solution

1class Solution {
2public:
3    // Function to modify the string by replacing '?' characters
4    string modifyString(string s) {
5        int n = s.size(); // Get the size of the string
6      
7        // Iterate over the characters of the string
8        for (int i = 0; i < n; ++i) {
9            // Check if the current character is '?'
10            if (s[i] == '?') {
11                // Iterate over the choices of 'a', 'b', and 'c'
12                for (char c : "abc") {
13                    // Check if choosing 'c' would violate the requirement (no same adjacent characters)
14                    if ((i > 0 && s[i - 1] == c) || (i + 1 < n && s[i + 1] == c)) {
15                        continue; // Skip this letter as it matches an adjacent character
16                    }
17                    // Found a valid replacement for '?', so set it and break out of the inner loop
18                    s[i] = c;
19                    break;
20                }
21            }
22        }
23        // Return the modified string
24        return s;
25    }
26};
27

Typescript Solution

1function modifyString(s: string): string {
2    // Create an array of characters from the input string.
3    const characters = s.split('');
4    // Determine the length of the string.
5    const length = s.length;
6
7    // Iterate through each character in the array.
8    for (let i = 0; i < length; ++i) {
9        // Check if the current character is a question mark.
10        if (characters[i] === '?') {
11            // Loop through the letters 'a', 'b', and 'c'.
12            for (const letter of 'abc') {
13                // If the previous character or the next character is the same as `letter`, skip to the next letter.
14                if ((i > 0 && characters[i - 1] === letter) || (i + 1 < length && characters[i + 1] === letter)) {
15                    continue;
16                }
17                // Replace the question mark with the current `letter` and exit the inner loop.
18                characters[i] = letter;
19                break;
20            }
21        }
22    }
23    // Join the array of characters back into a string and return it.
24    return characters.join('');
25}
26

Time and Space Complexity

Time Complexity

The given code loops through each character of the input string s exactly once, with a fixed number of operations per loop iteration (checking and possibly replacing a character). For each character that is "?", it attempts a maximum of three substitution checks – each check involves comparing against the previous and the next character in the string (if any).

Since the checking and substitution are constant-time operations and independent of the size of the string, we can determine that the inner loop has a constant time complexity of O(1) for each character. The outer loop runs n times, where n is the length of s.

Therefore, the time complexity is O(n), where n is the length of the string, because we perform a constant amount of work for each character in the string.

Space Complexity

The space complexity of the code is also dependent on the length of the input string s. This is because the string is converted to a list of characters to allow in-place modifications, which takes O(n) space, where n is the length of the input string. Apart from this, only a constant amount of additional space is used for variables i, c, and n.

Hence, the space complexity is O(n).


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫