1576. Replace All ?‘s to Avoid Consecutive Repeating Characters
Model: qwen2.5-coder:14b
Topics: String
FAANG asked: 1
Acceptance rate: 50.0%
Problem Breakdown
The problem requires us to replace all ’?’ characters in a given string s with lowercase English letters such that no two consecutive characters are the same. The input string contains only lowercase English letters and the ’?’ character. We need to ensure that after replacing all ’?’, the final string does not have any consecutive repeating characters. It is guaranteed that there are no consecutive repeating characters in the given string except for ’?’.
Inputs:
- A string
scontaining lowercase English letters and ’?’.
Outputs:
- A modified string where all ’?’ are replaced with lowercase English letters such that no two consecutive characters are the same.
Implicit Constraints:
- The length of the string is between 1 and 100.
- There will always be a valid solution to replace ’?’ without causing consecutive repeating characters.
Intuition
A brute-force approach would involve trying all possible combinations of replacing ’?’ with lowercase letters and checking for consecutive repeating characters. However, this approach is computationally expensive due to the factorial growth in possibilities (26^n where n is the number of ’?’).
The key insight is that for each ’?’, we can choose any letter from ‘a’ to ‘z’ except the one immediately before it and the one immediately after it. This reduces the problem to a linear scan with constant-time decisions for each ’?’.
Approach
- Iterate through each character in the string.
- If the character is ’?’:
- Determine the previous and next characters (if they exist).
- Choose a letter from ‘a’ to ‘z’ that is not equal to the previous or next character.
- Replace the ’?’ with this chosen letter.
- Continue until all ’?’ are replaced.
This approach ensures that we only make one pass through the string, making it efficient in terms of time complexity.
Complexity Analysis
- Time Complexity: O(n), where n is the length of the string. We iterate through each character once.
- Space Complexity: O(1) (excluding the input and output strings). We use a constant amount of extra space for variables.
Solution
def modifyString(s: str) -> str:
s = list(s) # Convert string to list for easy modification
chars = 'abcdefghijklmnopqrstuvwxyz'
for i in range(len(s)):
if s[i] == '?':
prev_char = s[i - 1] if i > 0 else ''
next_char = s[i + 1] if i < len(s) - 1 else ''
# Find a character that is not equal to the previous or next character
for char in chars:
if char != prev_char and char != next_char:
s[i] = char
break
return ''.join(s)
Edge Cases Handled
- Single Character String: If the string has only one character, it must be ’?’, which will be replaced by any letter from ‘a’ to ‘z’.
- Consecutive ’?’ Characters: The algorithm handles consecutive ’?’ characters by ensuring each ’?’ is replaced independently based on its immediate neighbors.
- No ’?’ in the String: If there are no ’?’ characters, the string remains unchanged.
- All ’?’ Characters: The algorithm will replace all ’?’ with valid letters without causing any consecutive repeating characters.