424. Longest Repeating Character Replacement LeetCode Solution
In this guide, you will get 424. Longest Repeating Character Replacement LeetCode Solution with the best time and space complexity. The solution to Longest Repeating Character Replacement problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Longest Repeating Character Replacement
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. You can perform this operation at most k times.
Return the length of the longest substring containing the same letter you can get after performing the above operations.
Example 1:
Input: s = “ABAB”, k = 2
Output: 4
Explanation: Replace the two ‘A’s with two ‘B’s or vice versa.
Example 2:
Input: s = “AABABBA”, k = 1
Output: 4
Explanation: Replace the one ‘A’ in the middle with ‘B’ and form “AABBBBA”.
The substring “BBBB” has the longest repeating letters, which is 4.
There may exists other ways to achieve this answer too.
Constraints:
1 <= s.length <= 105
s consists of only uppercase English letters.
0 <= k <= s.length
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(26) = O(1)
424. Longest Repeating Character Replacement LeetCode Solution in C++
class Solution {
public:
int characterReplacement(string s, int k) {
int ans = 0;
int maxCount = 0;
vector<int> count(26);
for (int l = 0, r = 0; r < s.length(); ++r) {
maxCount = max(maxCount, ++count[s[r] - 'A']);
while (maxCount + k < r - l + 1)
--count[s[l++] - 'A'];
ans = max(ans, r - l + 1);
}
return ans;
}
}; /* code provided by PROGIEZ */
424. Longest Repeating Character Replacement LeetCode Solution in Java
class Solution {
public int characterReplacement(String s, int k) {
int ans = 0;
int maxCount = 0;
int[] count = new int[26];
for (int l = 0, r = 0; r < s.length(); ++r) {
maxCount = Math.max(maxCount, ++count[s.charAt(r) - 'A']);
while (maxCount + k < r - l + 1)
--count[s.charAt(l++) - 'A'];
ans = Math.max(ans, r - l + 1);
}
return ans;
}
} // code provided by PROGIEZ
424. Longest Repeating Character Replacement LeetCode Solution in Python
class Solution:
def characterReplacement(self, s: str, k: int) -> int:
ans = 0
maxCount = 0
count = collections.Counter()
l = 0
for r, c in enumerate(s):
count[c] += 1
maxCount = max(maxCount, count[c])
while maxCount + k < r - l + 1:
count[s[l]] -= 1
l += 1
ans = max(ans, r - l + 1)
return ans # code by PROGIEZ
