Problem
https://leetcode.com/problems/longest-repeating-character-replacement/
Longest Repeating Character Replacement - LeetCode
Can you solve this real interview question? 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 operati
leetcode.com
Hint
Tyy using sliding window technique.
Solution
Code
Simple
class Solution {
public:
int characterReplacement(string s, int k) {
int n = s.size();
int answer = k+1;
vector<int> dp(26,0);
int maxIndex = 0;
for (int i=0, j=0; j<n; j++) {
// count char in dp
dp[s[j]-'A']++;
// get index of most popular char
if (dp[maxIndex] < dp[s[j]-'A']) {
maxIndex = s[j]-'A';
}
// slide window to right if (length of the substring - count of most popular char) > k
if (j - i + 1 - dp[maxIndex] > k) {
dp[s[i]-'A']--;
i++;
}
// j-i+1: length of current substring(window)
answer = max(answer, j-i+1);
}
return answer;
}
};Whole Code with Test Case
// https://leetcode.com/problems/longest-repeating-character-replacement
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
class Solution {
public:
int characterReplacement(string s, int k) {
int n = s.size();
int answer = k+1;
vector<int> dp(26,0);
int maxIndex = 0;
for (int i=0, j=0; j<n; j++) {
// count char in dp
dp[s[j]-'A']++;
// get index of most popular char
if (dp[maxIndex] < dp[s[j]-'A']) {
maxIndex = s[j]-'A';
}
// slide window to right if (length of the substring - count of most popular char) > k
if (j - i + 1 - dp[maxIndex] > k) {
dp[s[i]-'A']--;
i++;
}
// j-i+1: length of current substring(window)
answer = max(answer, j-i+1);
}
return answer;
}
};
int main() {
Solution s = Solution();
cout << s.characterReplacement("AABABBA", 1) << endl;
}
Complexity
Time
Time complexity will be O(n).
Space
Space complexity will be O(1).
Best Solution (Pinned)
Overall
