Problem Statement
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
Example 1:
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.Example 2:
Input : s = "AABABBA", k = 1
Output : 4
Explanation : Change the A present at index 3.
The new string is "AABBBBA". The substring "BBBB" is the answer.
There are other ways to achieve this answer.Different Approaches
1️⃣ Brute Force Approach
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 encountered so far.
Approach:
- First, initialize few variables: 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.
- Iterate through the array, which will basically be the starting point of the substring. For each starting index, initialize a frequency array hash to count occurrences of characters.
- Update max frequency encountered and store it in maxFreq variable. Calculate the number of changes needed to make.
- Which would be
length - maxFreq. Because we would like to change the character with the least frequency.
- Which would be
- If changes is less than or equal to k, update maxLen with the size of the current valid window. If changes exceeds k, break out of the inner loop since further expanding the window won't help in achieving a valid substring. Finally return the maxLen as a answer.
Code:
#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;
}Complexity Analysis:
- Time Complexity:
O(N^2), whereNis 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.
2️⃣ Better Approach
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:
- First initialize few variables: 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.
- Incrementally expand the window by moving the r pointer to the right. Update the frequency of the current character in hash and adjust maxFreq if this frequency exceeds the current maxFreq.
- Check if the number of characters that need replacement exceeds k. If so, slide the l pointer to the right until the window becomes valid again. Adjust the frequencies in hash and update maxFreq accordingly.
- After ensuring the window is valid, update maxLen with the length of the current window. Finally, return maxLen, which holds the length of the longest substring.
Code:
#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;
}
Complexity Analysis:
- Time Complexity:
O((N+N) * 26), whereNis the size of the array. The right pointer runs forNtimes and the left pointer runs forNtimes throughout. The for loop takes extraO(26)to calculate the maximum frequency. - Space Complexity:
O(26). Hash array to store all the characters.
3️⃣ Optimal Approach
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:
- First, initialize few variables: /code>(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.
- Incrementally expand the window by moving the r pointer to the right. Update the frequency count of current character. Track the maximum frequency encountered (maxFreq) within the current window.
- If the length of the current window minus maxFreq exceeds k, the window becomes invalid. Slide the l pointer to the right to shrink the window until it becomes valid again by decrementing the frequency count of character at left pointer.
- After ensuring the window is valid, update maxLen with the length of the current window. continue this process until the r pointer reaches the end of the string and finally, return maxLen as an answer.
Code:
#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;
}
Complexity Analysis:
- Time Complexity:
O(N), whereNis the size of the array. The right pointer runs for N times. - Space Complexity:
O(26),Hash array to store all the characters.