Longest Repeating Character Replacement — LeetCode 424 Python Solution
MediumHash TableStringSliding Window
- Problem
- #424
- Pattern
- Sliding Window
- Reading time
- 2 min
- Source
- leetcode.com
The problem
You are given a string s and an integer k. You can choose any character of the string and change it to any other uppercase English character.
Example
- Input
- s = "ABAB", k = 2
- Output
- 4
- Explanation
- Replace the two 'A's with two 'B's or vice versa.
Python solution
Python
class Solution:
def characterReplacement(self, s: str, k: int) -> int:
cnt = Counter()
l = mx = 0
for r, c in enumerate(s):
cnt[c] += 1
mx = max(mx, cnt[c])
if r - l + 1 - mx > k:
cnt[s[l]] -= 1
l += 1
return len(s) - lComplexity
| Measure | Complexity |
|---|---|
| Time | O(n) |
| Space | O(|\Sigma|) auxiliary |
Pattern: Sliding Window
Collapse a nested loop over every subarray into a single pass with two indices. LeetCode 424. Longest Repeating Character Replacement is filed here because LeetCode tags it Sliding Window, which is the vocabulary this hub collects.
The sliding window guide has the Python template for the pattern and the 116 LeetCode problems that use it.
Related problems
LeetCode 3Longest Substring Without Repeating CharactersMediumLeetCode 30Substring with Concatenation of All WordsHardLeetCode 76Minimum Window SubstringHardLeetCode 187Repeated DNA SequencesMediumLeetCode 395Longest Substring with At Least K Repeating CharactersMediumLeetCode 438Find All Anagrams in a StringMedium
On study lists
This problem is on Blind 75 and NeetCode 150.
Frequently asked questions
- How hard is LeetCode 424. Longest Repeating Character Replacement?
- LeetCode 424. Longest Repeating Character Replacement is rated Medium on LeetCode.
- What is the time complexity of LeetCode 424. Longest Repeating Character Replacement?
- The Python solution on this page runs in O(n).
- What is the space complexity of LeetCode 424. Longest Repeating Character Replacement?
- The Python solution on this page uses O(|\Sigma|) auxiliary space.
- What topics does LeetCode 424. Longest Repeating Character Replacement cover?
- LeetCode 424. Longest Repeating Character Replacement is tagged Hash Table, String and Sliding Window on LeetCode.