EasyNo. 1576
Replace All ?'s to Avoid Consecutive Repeating Characters — LeetCode 1576 Python Solution
- Pattern
- Hash Map
- Topics
- String
- Reading time
- 2 min
- Source
- leetcode.com
The 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.
Example
- 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".
Python solution
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)Complexity
- Time
- O(n)
- Space · auxiliary
- O(1) to O(n)
Pattern: Hash Map
Trade memory for time: remember what you have seen so the second pass never happens. LeetCode 1576. Replace All ?'s to Avoid Consecutive Repeating Characters is filed here because the reference solution below belongs to the algorithm family this hub collects, even though its LeetCode tags point elsewhere.
The hash map guide has the Python template for the pattern and the 709 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0006 | Zigzag Conversion | Medium |
| 0008 | String to Integer (atoi) | Medium |
| 0038 | Count and Say | Medium |
| 0058 | Length of Last Word | Easy |
| 0065 | Valid Number | Hard |
| 0068 | Text Justification | Hard |
Frequently asked questions
- How hard is LeetCode 1576. Replace All ?'s to Avoid Consecutive Repeating Characters?
LeetCode 1576. Replace All ?'s to Avoid Consecutive Repeating Characters is rated Easy on LeetCode.
- What topics does LeetCode 1576. Replace All ?'s to Avoid Consecutive Repeating Characters cover?
LeetCode 1576. Replace All ?'s to Avoid Consecutive Repeating Characters is tagged String on LeetCode.