Longest Repeating Character Replacement
Sliding Window / 2 Pointer
Longest and Smallest Window Problems
Hard
- This problem is highly relevant in search engine algorithms, particularly those dealing with text analysis and processing
- The ability to manipulate and understand strings to achieve certain conditions is central to many features, such as autocomplete functions, spell checkers, and text-based recommendation algorithms
- For example, Google's Search engine may use similar principles to understand and autocorrect your typos to give you accurate search results
Given an integer k and a string s, any character in the string can be selected and changed to any other uppercase English character. This operation can be performed up to k times. After completing these steps, return the length of the longest substring that contains the same letter.
Examples:
Input : s = "BAABAABBBAAA" , k = 2
Output : 6
Explanation : we can change the B present at index 0 , 3 (0 base indexing) to A.
The new string is "AAAAAABBBAAA".
The substring "AAAAAA" is the longest substring having same letter with length 6.
Input : s = "AABABBA" , k = 1
Output : 4
Explanation : The underlined characters are changed in the new string obtained.
The new string is "AABBBBA". The substring "BBBB" is the answer.
There are other ways to achieve this answer.
Input : s = "ABCDEF" k = 1
Constraints
- 1 <= s.length <= 105
- 0 <= k <= s.length
- s contains only English uppercase letters.
Hints
- Use a sliding window to find the longest substring where at most k characters are replaced to make all characters in the substring the same.
- Calculate the number of replacements needed to make all characters in the window the same as window_size−max_freq.
Company Tags
Western Digital
Pinterest
Target
Epic Systems
Freshworks
Texas Instruments
Square
Byju's
Databricks
PayPal
Cloudflare
Boston Consulting Group
Zoho
Splunk
Shopify
Riot Games
Oracle
PwC
Micron Technology
Roche
NVIDIA
Flipkart
Philips Healthcare
Uber
HashiCorp
Google
Microsoft
Amazon
Meta
Apple
Netflix
Adobe
Editorial
Intuition:
The thought process is very straightforward, first find out each and every substring and while doing so, keep a track of characters and their frequencies. Further, calculate the number of characters that needs to be changed, if it is greater than the given limit then no need to consider that substring, else calculate the maximum length of the substring encountred so far.
Approach:
maxLen as 0 to track the maximum length found and maxFreq as 0 to track the highest frequency of any single character in the current window.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
/*Function to find the longest substring
with at most k characters replaced.*/
int characterReplacement(string s, int k) {
/* Variable to store the maximum
length of substring found*/
int maxLen = 0;
/* Variable to track the maximum frequency
of any single character in the current window*/
int maxFreq = 0;
// Iterate through each starting point of the substring
for (int i = 0; i < s.size(); ++i) {
// Initialize hash array for character frequencies
int hash[26] = {0};
for (int j = i; j < s.size(); ++j) {
/* Update frequency of current
character in the hash array*/
hash[s[j] - 'A']++;
// Update max frequency encountered
maxFreq = max(maxFreq, hash[s[j] - 'A']);
// Calculate the number of changes needed to make
int changes = (j - i + 1) - maxFreq;
/* If the number of changes is less than or
equal to k, the current window is valid*/
if (changes <= k) {
maxLen = max(maxLen, j - i + 1);
}
else break;
}
}
/* Return the maximum length of substring
with at most k characters replaced*/
return maxLen;
}
};
int main() {
string s = "AABABBA";
int k = 2;
// Create an instance of Solution class
Solution sol;
int length = sol.characterReplacement(s, k);
// Print the result
cout << "Maximum length of substring with at most " << k << " characters replaced: " << length << endl;
return 0;
}
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162
import java.util.*;
class Solution {
/*Function to find the longest substring
with at most k characters replaced.*/
public int characterReplacement(String s, int k) {
/* Variable to store the maximum
length of substring found*/
int maxLen = 0;
/* Variable to track the maximum frequency
of any single character in the current window*/
int maxFreq = 0;
// Iterate through each starting point of the substring
for (int i = 0; i < s.length(); ++i) {
// Initialize hash array for character frequencies
int[] hash = new int[26];
for (int j = i; j < s.length(); ++j) {
/* Update frequency of current
character in the hash array*/
hash[s.charAt(j) - 'A']++;
// Update max frequency encountered
maxFreq = Math.max(maxFreq, hash[s.charAt(j) - 'A']);
// Calculate number of changes needed to make
int changes = (j - i + 1) - maxFreq;
/* If the number of changes is less than
or equal to k, the current window is valid*/
if (changes <= k) {
maxLen = Math.max(maxLen, j - i + 1);
} else {
break;
}
}
}
/* Return the maximum length of substring
with at most k characters replaced*/
return maxLen;
}
public static void main(String[] args) {
String s = "AABABBA";
int k = 2;
// Create an instance of Solution class
Solution sol = new Solution();
int length = sol.characterReplacement(s, k);
// Print the result
System.out.println("Maximum length of substring with at most " + k + " characters replaced: " + length);
}
}
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556
class Solution:
"""
Function to find the longest substring
with at most k characters replaced.
"""
def characterReplacement(self, s: str, k: int) -> int:
""" Variable to store the maximum
length of substring found"""
maxLen = 0
""" Variable to track the maximum frequency of
any single character in the current window"""
maxFreq = 0
# Iterate through each starting point of the substring
for i in range(len(s)):
# Initialize hash array for character frequencies
hash = [0] * 26
for j in range(i, len(s)):
""" Update frequency of current
character in the hash array"""
hash[ord(s[j]) - ord('A')] += 1
# Update max frequency encountered
maxFreq = max(maxFreq, hash[ord(s[j]) - ord('A')])
# Calculate the number of changes needed to make
changes = (j - i + 1) - maxFreq
""" If the number of changes is less than or
equal to k, the current window is valid"""
if changes <= k:
maxLen = max(maxLen, j - i + 1)
else:
break
""" Return the maximum length of substring
with at most k characters replaced"""
return maxLen
if __name__ == "__main__":
s = "AABABBA"
k = 2
# Create an instance of Solution class
sol = Solution()
length = sol.characterReplacement(s, k)
# Print the result
print(f"Maximum length of substring with at most {k} characters replaced: {length}")
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859
class Solution {
/* Function to find the longest substring
with at most k characters replaced.*/
characterReplacement(s, k) {
/* Variable to store the maximum
length of substring found*/
let maxLen = 0;
/* Variable to track the maximum frequency of
any single character in the current window*/
let maxFreq = 0;
// Iterate through each starting point of the substring
for (let i = 0; i < s.length; ++i) {
// Initialize hash array for character frequencies
let hash = new Array(26).fill(0);
for (let j = i; j < s.length; ++j) {
/* Update frequency of current
character in the hash array*/
hash[s.charCodeAt(j) - 'A'.charCodeAt(0)]++;
// Update max frequency encountered
maxFreq = Math.max(maxFreq, hash[s.charCodeAt(j) - 'A'.charCodeAt(0)]);
// Calculate the number of changes needed to make
let changes = (j - i + 1) - maxFreq;
/* If the number of changes is less than or
equal to k, the current window is valid*/
if (changes <= k) {
maxLen = Math.max(maxLen, j - i + 1);
}
else break;
}
}
/* Return the maximum length of substring
with at most k characters replaced*/
return maxLen;
}
}
// Example usage:
let s = "AABABBA";
let k = 2;
// Create an instance of Solution class
let sol = new Solution();
let len = sol.characterReplacement(s, k);
// Print the result
console.log(`Maximum length of substring with at most ${k} characters replaced: ${len}`);
Complexity Analysis:
Time Complexity:O(N2), where N is the size of the array. Iterating the array twice using two for loops.Space Complexity: O(26) . Hash array to store the frequencies of the capital letters.
Intuition:
The idea here is to use the sliding window technique to solve this problem optimally. This method efficiently finds the longest substring with frequency counting and dynamic adjustments to ensure validity of the window. First expand the window and add those substring that validates the cndition and when it crosses the limit, again shrink the window by moving the left pointer. This process ensures to provide a linear time complexity.
Approach:
l (left) and r (right) as 0 to define the current window in the string, maxLen as 0 to track the maximum length of valid substrings, maxFreq as 0 to monitor the highest frequency of any single character within the current window. Also, maintain a frequency array hash to count occurrences of characters.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
/*Function to find the longest substring
with at most k characters replaced*/
int characterReplacement(string s, int k) {
/* Variable to store the maximum
length of substring found*/
int maxLen = 0;
/* Variable to track the maximum frequency
of any single character in the current window*/
int maxFreq = 0;
//Pointers to maintain the current window [l, r]
int l = 0, r = 0;
// Hash array to count frequencies of characters
int hash[26] = {0};
// Iterate through each starting point of substring
while (r < s.size()) {
/* Update frequency of current
character in the hash array*/
hash[s[r] - 'A']++;
// Update max frequency encountered
maxFreq = max(maxFreq, hash[s[r] - 'A']);
// Check if current window is invalid
while ((r - l + 1) - maxFreq > k) {
/* Slide the left pointer to
make the window valid again*/
hash[s[l] - 'A']--;
// Recalculate maxFreq for current window
maxFreq = 0;
for (int i = 0; i < 26; ++i) {
maxFreq = max(maxFreq, hash[i]);
}
// Move left pointer forward
l++;
}
/* Update maxLen with the length
of the current valid substring*/
maxLen = max(maxLen, r - l + 1);
// Move right pointer forward to expand the window
r++;
}
/* Return the maximum length of substring
with at most k characters replaced*/
return maxLen;
}
};
int main() {
string s = "AABABBA";
int k = 2;
// Create an instance of Solution class
Solution sol;
int length = sol.characterReplacement(s, k);
// Print the result
cout << "Maximum length of substring with at most " << k << " characters replaced: " << length << endl;
return 0;
}
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273
import java.util.*;
class Solution {
/*Function to find the longest substring
with at most k characters replaced*/
public int characterReplacement(String s, int k) {
/* Variable to store the maximum
length of substring found*/
int maxLen = 0;
/* Variable to track the maximum frequency
of any single character in the current window*/
int maxFreq = 0;
// Pointers to maintain the current window [l, r]
int l = 0, r = 0;
// Hash array to count frequencies of characters
int[] hash = new int[26];
// Iterate through each starting point of substring
while (r < s.length()) {
/* Update frequency of current
character in the hash array*/
hash[s.charAt(r) - 'A']++;
// Update max frequency encountered
maxFreq = Math.max(maxFreq, hash[s.charAt(r) - 'A']);
// Check if current window is invalid
while ((r - l + 1) - maxFreq > k) {
/* Slide the left pointer to
make the window valid again*/
hash[s.charAt(l) - 'A']--;
// Recalculate maxFreq for current window
maxFreq = 0;
for (int i = 0; i < 26; ++i) {
maxFreq = Math.max(maxFreq, hash[i]);
}
// Move left pointer forward
l++;
}
/* Update maxLen with the length
of the current valid substring*/
maxLen = Math.max(maxLen, r - l + 1);
// Move right pointer forward to expand window
r++;
}
/* Return the maximum length of substring
with at most k characters replaced*/
return maxLen;
}
public static void main(String[] args) {
String s = "AABABBA";
int k = 2;
// Create an instance of Solution class
Solution sol = new Solution();
int length = sol.characterReplacement(s, k);
// Print the result
System.out.println("Maximum length of substring with at most " + k + " characters replaced: " + length);
}
}
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970
class Solution:
"""
Function to find the longest substring
with at most k characters replaced
"""
def characterReplacement(self, s: str, k: int) -> int:
""" Variable to store the maximum
length of substring found"""
maxLen = 0
""" Variable to track the maximum frequency
of any single character in the current window"""
maxFreq = 0
# Pointers to maintain the current window [l, r]
l = 0
r = 0
# Hash array to count frequencies of characters
hash = [0] * 26
# Iterate through each starting point of substring
while r < len(s):
""" Update frequency of current
character in the hash array"""
hash[ord(s[r]) - ord('A')] += 1
# Update max frequency encountered
maxFreq = max(maxFreq, hash[ord(s[r]) - ord('A')])
# Check if current window is invalid
while (r - l + 1) - maxFreq > k:
""" Slide the left pointer to
make the window valid again"""
hash[ord(s[l]) - ord('A')] -= 1
# Recalculate maxFreq for current window
maxFreq = 0
for i in range(26):
maxFreq = max(maxFreq, hash[i])
# Move left pointer forward
l += 1
""" Update maxLen with the length
of the current valid substring"""
maxLen = max(maxLen, r - l + 1)
# Move right pointer forward to expand window
r += 1
""" Return the maximum length of substring
with at most k characters replaced"""
return maxLen
if __name__ == "__main__":
s = "AABABBA"
k = 2
# Create an instance of Solution class
sol = Solution()
length = sol.characterReplacement(s, k)
# Print the result
print(f"Maximum length of substring with at most {k} characters replaced: {length}")
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869
class Solution {
/*Function to find the longest substring
with at most k characters replaced*/
characterReplacement(s, k) {
/* Variable to store the maximum
length of substring found*/
let maxLen = 0;
/* Variable to track the maximum frequency
of any single character in the current window*/
let maxFreq = 0;
// Pointers to maintain the current window [l, r]
let l = 0, r = 0;
// Hash array to count frequencies of characters
let hash = new Array(26).fill(0);
// Iterate through each starting point of substring
while (r < s.length) {
/* Update frequency of current
character in the hash array*/
hash[s.charCodeAt(r) - 'A'.charCodeAt(0)]++;
// Update max frequency encountered
maxFreq = Math.max(maxFreq, hash[s.charCodeAt(r) - 'A'.charCodeAt(0)]);
// Check if current window is invalid
while ((r - l + 1) - maxFreq > k) {
// Slide the left pointer to make the window valid again
hash[s.charCodeAt(l) - 'A'.charCodeAt(0)]--;
// Recalculate maxFreq for current window
maxFreq = 0;
for (let i = 0; i < 26; ++i) {
maxFreq = Math.max(maxFreq, hash[i]);
}
// Move left pointer forward
l++;
}
/* Update maxLen with the length
of the current valid substring*/
maxLen = Math.max(maxLen, r - l + 1);
// Move right pointer forward to expand window
r++;
}
/* Return the maximum length of substring
with at most k characters replaced*/
return maxLen;
}
}
let s = "AABABBA";
let k = 2;
// Create an instance of Solution class
let sol = new Solution();
let len = sol.characterReplacement(s, k);
// Print the result
console.log(`Maximum length of substring with at most ${k} characters replaced: ${len}`);
Complexity Analysis:
Time Complexity:O((N+N) * 26), where N is the size of the array. The right pointer runs for N times and the left pointer runs for N times throughout. The for loop takes extra O(26) to claculate the maximum frequency.Space Complexity: O(26) . Hash array to store all the characters.
Intuition:
The idea here is to use the sliding window approach by avoiding the additional O(N) time complexity incurred when shifting the window entirely in the Better solution, to ensure that no more than k characters gets replaced in the current substring. Instead of moving the left pointer (l) completely till the distinct character comes under given limit, shift the window by one position at a time. This way the extra while loop used in Optimal I approach can be eliminated.
Approach:
l(left) and r (right) as 0 to define the current window in the string, maxLen as 0 to track the maximum length of valid substrings. Also, maintain a frequency array hash to count occurrences of characters.
Dry Run:
Please refer to the video for complete dry-run.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
/*Function to find the longest substring
with at most k characters replaced*/
int characterReplacement(string s, int k) {
/* Variable to store the maximum
length of substring found*/
int maxLen = 0;
/* Variable to track the maximum frequency
of any single character in the current window*/
int maxFreq = 0;
//Pointers to maintain the current window [l, r]
int l = 0, r = 0;
// Hash array to count frequencies of characters
int hash[26] = {0};
// Iterate through each starting point of substring
while (r < s.size()) {
/* Update frequency of current
character in the hash array*/
hash[s[r] - 'A']++;
// Update max frequency encountered
maxFreq = max(maxFreq, hash[s[r] - 'A']);
// Check if current window is invalid
if ((r - l + 1) - maxFreq > k) {
/* Slide the left pointer to
make the window valid again*/
hash[s[l] - 'A']--;
// Move left pointer forward
l++;
}
/* Update maxLen with the length
of the current valid substring*/
maxLen = max(maxLen, r - l + 1);
// Move right pointer forward to expand the window
r++;
}
/* Return the maximum length of substring
with at most k characters replaced*/
return maxLen;
}
};
int main() {
string s = "AABABBA";
int k = 2;
// Create an instance of Solution class
Solution sol;
int length = sol.characterReplacement(s, k);
// Print the result
cout << "Maximum length of substring with at most " << k << " characters replaced: " << length << endl;
return 0;
}
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667
import java.util.*;
class Solution {
/*Function to find the longest substring
with at most k characters replaced*/
public int characterReplacement(String s, int k) {
/* Variable to store the maximum
length of substring found*/
int maxLen = 0;
/* Variable to track the maximum frequency
of any single character in the current window*/
int maxFreq = 0;
// Pointers to maintain the current window [l, r]
int l = 0, r = 0;
// Hash array to count frequencies of characters
int[] hash = new int[26];
// Iterate through each starting point of substring
while (r < s.length()) {
/* Update frequency of current
character in the hash array*/
hash[s.charAt(r) - 'A']++;
// Update max frequency encountered
maxFreq = Math.max(maxFreq, hash[s.charAt(r) - 'A']);
// Check if current window is invalid
if ((r - l + 1) - maxFreq > k) {
/* Slide the left pointer to
make the window valid again*/
hash[s.charAt(l) - 'A']--;
// Move left pointer forward
l++;
}
/* Update maxLen with the length
of the current valid substring*/
maxLen = Math.max(maxLen, r - l + 1);
// Move right pointer forward to expand window
r++;
}
/* Return the maximum length of substring
with at most k characters replaced*/
return maxLen;
}
public static void main(String[] args) {
String s = "AABABBA";
int k = 2;
// Create an instance of Solution class
Solution sol = new Solution();
int length = sol.characterReplacement(s, k);
// Print the result
System.out.println("Maximum length of substring with at most " + k + " characters replaced: " + length);
}
}
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465
class Solution:
"""
Function to find the longest substring
with at most k characters replaced
"""
def characterReplacement(self, s: str, k: int) -> int:
""" Variable to store the maximum
length of substring found"""
maxLen = 0
""" Variable to track the maximum frequency
of any single character in the current window"""
maxFreq = 0
# Pointers to maintain the current window [l, r]
l = 0
r = 0
# Hash array to count frequencies of characters
hash = [0] * 26
# Iterate through each starting point of substring
while r < len(s):
""" Update frequency of current
character in the hash array"""
hash[ord(s[r]) - ord('A')] += 1
# Update max frequency encountered
maxFreq = max(maxFreq, hash[ord(s[r]) - ord('A')])
# Check if current window is invalid
if (r - l + 1) - maxFreq > k:
""" Slide the left pointer to
make the window valid again"""
hash[ord(s[l]) - ord('A')] -= 1
# Move left pointer forward
l += 1
""" Update maxLen with the length
of the current valid substring"""
maxLen = max(maxLen, r - l + 1)
# Move right pointer forward to expand window
r += 1
""" Return the maximum length of substring
with at most k characters replaced"""
return maxLen
if __name__ == "__main__":
s = "AABABBA"
k = 2
# Create an instance of Solution class
sol = Solution()
length = sol.characterReplacement(s, k)
# Print the result
print(f"Maximum length of substring with at most {k} characters replaced: {length}")
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263
class Solution {
/*Function to find the longest substring
with at most k characters replaced*/
characterReplacement(s, k) {
/* Variable to store the maximum
length of substring found*/
let maxLen = 0;
/* Variable to track the maximum frequency
of any single character in the current window*/
let maxFreq = 0;
// Pointers to maintain the current window [l, r]
let l = 0, r = 0;
// Hash array to count frequencies of characters
let hash = new Array(26).fill(0);
// Iterate through each starting point of substring
while (r < s.length) {
/* Update frequency of current
character in the hash array*/
hash[s.charCodeAt(r) - 'A'.charCodeAt(0)]++;
// Update max frequency encountered
maxFreq = Math.max(maxFreq, hash[s.charCodeAt(r) - 'A'.charCodeAt(0)]);
// Check if current window is invalid
if ((r - l + 1) - maxFreq > k) {
// Slide the left pointer to make the window valid again
hash[s.charCodeAt(l) - 'A'.charCodeAt(0)]--;
// Move left pointer forward
l++;
}
/* Update maxLen with the length
of the current valid substring*/
maxLen = Math.max(maxLen, r - l + 1);
// Move right pointer forward to expand window
r++;
}
/* Return the maximum length of substring
with at most k characters replaced*/
return maxLen;
}
}
let s = "AABABBA";
let k = 2;
// Create an instance of Solution class
let sol = new Solution();
let len = sol.characterReplacement(s, k);
// Print the result
console.log(`Maximum length of substring with at most ${k} characters replaced: ${len}`);
Complexity Analysis:
Time Complexity:O(N), where N is the size of the array. The right pointer runs for N times.Space Complexity: O(26) . Hash array to store all the characters.
Frequently Occurring Doubts
Q: How is the replacement count calculated?
A: The replacement count for a window is the total number of characters in the window minus the frequency of the most common character. This represents the number of characters that need to be changed.
Q: What happens if all characters in the string are the same?
A: If all characters are identical, the entire string is valid without any replacements. The output is the length of the string.
Interview Followup Questions
Q: How would you handle lowercase letters or a mix of uppercase and lowercase?
A: Adjust the frequency map to account for 52 characters (26 lowercase + 26 uppercase), or normalize the case before processing.
Q: What if you wanted to return the actual substring instead of its length?
A: Track the start and end indices of the window whenever a new maximum length is found. Use these indices to extract the substring after completing the algorithm.
Notes
Code
✅ Testcase
Input: {'k': '2', 's': 'BAABAABBBAAA'}
Expected:
6
6
Actual: -
Time: -
sec
Status: Waiting
Input: {'k': '1', 's': 'AABABBA'}
Expected:
4
4
Actual: -
Time: -
sec
Status: Waiting
Input: {'k': '3', 's': 'ABAFEABBRADA'}
Expected:
6
6
Actual: -
Time: -
sec
Status: Waiting