Longest Repeating Character Replacement
Finding Longest Repeating Character Replacement Problem
You are given a string s that contains only uppercase English letters and an integer k. Your task is to determine the length of the longest substring in s that can consist of just one distinct character after modifying the string.
You are allowed to make up to k replacements, where each replacement involves changing any character in the substring to another uppercase English letter.
The goal is to maximize the length of this uniform substring by carefully choosing which characters to replace while staying within the limit of k changes.
Output: 4
Explanation : Either replace the ‘X’s with ‘Y’s, or replace the ‘Y’s with ‘X’s.
Output: 5
Constraints:
- 1 <= s.length <= 1000
- 0 <= k <= s.length
Finding Longest Repeating Character Replacement Solution
Recommendation for Time and Space Complexity – You should aim for a solution with O(n) time and O(m) space, where n is the length of the given string and m is the number of unique characters in the string.
Hints for solving problems
Hint 1 :
Which characters would you replace in a string to make all its characters unique? Can you think with respect to the frequency of the characters?
Hint 2 :
It is always optimal to replace characters with the most frequent character in the string. Why? Because using the most frequent character minimizes the number of replacements required to make all characters in the string identical. How can you find the number of replacements now?
There are mainly 3 approach to solve this problem-
- Brute Force Method
- Sliding Window Method
- Sliding Window Mehtod(Optimal)
1. Brute Force Method
Generate all possible substrings and check how many replacements are needed for each. Track the longest substring where replacements do not exceed the allowed limit.
- Time complexity: O(n^2)
- Space complexity: O(m)
where n is the length of the string and m is the total number of unique characters in the string.
Code
class Solution {
public:
int characterReplacement(string s, int k) {
int res = 0;
for (int i = 0; i < s.size(); i++) {
unordered_map count;
int maxf = 0;
for (int j = i; j < s.size(); j++) {
count[s[j]]++;
maxf = max(maxf, count[s[j]]);
if ((j - i + 1) - maxf <= k) {
res = max(res, j - i + 1);
}
}
}
return res;
}
};
public class Solution {
public int characterReplacement(String s, int k) {
int res = 0;
for (int i = 0; i < s.length(); i++) {
HashMap count = new HashMap<>();
int maxf = 0;
for (int j = i; j < s.length(); j++) {
count.put(s.charAt(j), count.getOrDefault(s.charAt(j), 0) + 1);
maxf = Math.max(maxf, count.get(s.charAt(j)));
if ((j - i + 1) - maxf <= k) {
res = Math.max(res, j - i + 1);
}
}
}
return res;
}
}
class Solution:
def characterReplacement(self, s: str, k: int) -> int:
res = 0
for i in range(len(s)):
count, maxf = {}, 0
for j in range(i, len(s)):
count[s[j]] = 1 + count.get(s[j], 0)
maxf = max(maxf, count[s[j]])
if (j - i + 1) - maxf <= k:
res = max(res, j - i + 1)
return res
class Solution {
/**
* @param {string} s
* @param {number} k
* @return {number}
*/
characterReplacement(s, k) {
let res = 0;
for (let i = 0; i < s.length; i++) {
let count = new Map();
let maxf = 0;
for (let j = i; j < s.length; j++) {
count.set(s[j], (count.get(s[j]) || 0) + 1);
maxf = Math.max(maxf, count.get(s[j]));
if ((j - i + 1) - maxf <= k) {
res = Math.max(res, j - i + 1);
}
}
}
return res;
}
}
2. Sliding Window Method
Maintain a sliding window and expand it to include more characters. If the number of characters to replace exceeds the limit, shrink the window from the left. Track the longest valid window during this process.
- Time complexity: O(m*n)
- Space complexity: O(m)
where n is the length of the string and m is the total number of unique characters in the string.
Code
class Solution {
public:
int characterReplacement(std::string s, int k) {
int res = 0;
unordered_set charSet(s.begin(), s.end());
for (char c : charSet) {
int count = 0, l = 0;
for (int r = 0; r < s.size(); r++) {
if (s[r] == c) {
count++;
}
while ((r - l + 1) - count > k) {
if (s[l] == c) {
count--;
}
l++;
}
res = std::max(res, r - l + 1);
}
}
return res;
}
};
public class Solution {
public int characterReplacement(String s, int k) {
int res = 0;
HashSet charSet = new HashSet<>();
for (char c : s.toCharArray()) {
charSet.add(c);
}
for (char c : charSet) {
int count = 0, l = 0;
for (int r = 0; r < s.length(); r++) {
if (s.charAt(r) == c) {
count++;
}
while ((r - l + 1) - count > k) {
if (s.charAt(l) == c) {
count--;
}
l++;
}
res = Math.max(res, r - l + 1);
}
}
return res;
}
}
class Solution:
def characterReplacement(self, s: str, k: int) -> int:
res = 0
charSet = set(s)
for c in charSet:
count = l = 0
for r in range(len(s)):
if s[r] == c:
count += 1
while (r - l + 1) - count > k:
if s[l] == c:
count -= 1
l += 1
res = max(res, r - l + 1)
return res
class Solution {
/**
* @param {string} s
* @param {number} k
* @return {number}
*/
characterReplacement(s, k) {
let res = 0;
let charSet = new Set(s);
for (let c of charSet) {
let count = 0, l = 0;
for (let r = 0; r < s.length; r++) {
if (s[r] === c) {
count++;
}
while ((r - l + 1) - count > k) {
if (s[l] === c) {
count--;
}
l++;
}
res = Math.max(res, r - l + 1);
}
}
return res;
}
}
3. Sliding Window Method(Optimal)
Track the frequency of characters within the sliding window. If the window size minus the count of the most frequent character exceeds the allowed replacements, adjust the window size. This method ensures efficient computation by focusing on the most frequent character and minimizing unnecessary replacements.
- Time complexity: O(n)
- Space complexity: O(m)
where n is the length of the string and m is the total number of unique characters in the string.
Code
class Solution {
public:
int characterReplacement(std::string s, int k) {
unordered_map count;
int res = 0;
int l = 0, maxf = 0;
for (int r = 0; r < s.size(); r++) {
count[s[r]]++;
maxf = max(maxf, count[s[r]]);
while ((r - l + 1) - maxf > k) {
count[s[l]]--;
l++;
}
res = max(res, r - l + 1);
}
return res;
}
};
public class Solution {
public int characterReplacement(String s, int k) {
HashMap count = new HashMap<>();
int res = 0;
int l = 0, maxf = 0;
for (int r = 0; r < s.length(); r++) {
count.put(s.charAt(r), count.getOrDefault(s.charAt(r), 0) + 1);
maxf = Math.max(maxf, count.get(s.charAt(r)));
while ((r - l + 1) - maxf > k) {
count.put(s.charAt(l), count.get(s.charAt(l)) - 1);
l++;
}
res = Math.max(res, r - l + 1);
}
return res;
}
}
class Solution:
def characterReplacement(self, s: str, k: int) -> int:
count = {}
res = 0
l = 0
maxf = 0
for r in range(len(s)):
count[s[r]] = 1 + count.get(s[r], 0)
maxf = max(maxf, count[s[r]])
while (r - l + 1) - maxf > k:
count[s[l]] -= 1
l += 1
res = max(res, r - l + 1)
return res
class Solution {
/**
* @param {string} s
* @param {number} k
* @return {number}
*/
characterReplacement(s, k) {
let count = new Map();
let res = 0;
let l = 0, maxf = 0;
for (let r = 0; r < s.length; r++) {
count.set(s[r], (count.get(s[r]) || 0) + 1);
maxf = Math.max(maxf, count.get(s[r]));
while ((r - l + 1) - maxf > k) {
count.set(s[l], count.get(s[l]) - 1);
l++;
}
res = Math.max(res, r - l + 1);
}
return res;
}
}
