Sliding Window: Longest substring after character replacement

Problem Statement:

You are given a string S and a value K.

You need to make K changes, so that the longest substring will have the same repeating character.

Example:

Input: S = ABABA, K = 2

Output: 5

Explanation: Replace 2 B with A. 

Solution Explanation:

We will solve the issue with the help of sliding window approach.

Take 2 pointers i and j that will define the window.

Expand j for new characters, and shrink i when replacement exceeds k.

maxi will track the count of most frequency character and if “window size – maxi > k”, then shrink window.

Keep track of the maximum and return the result.

Time Complexity: O(1)
Space Complexity: O(1)

Code Solution

#include <iostream>
#include <vector>
#include <unordered_map>
#include <queue>
#include <algorithm>
#include <climits>
using namespace std;

int solution(string s, int k) 
{
    int n = s.size();
    int i = 0, j = 0, maxi = 0;
    unordered_map<char,int> mp;
    int ans = -1;

    while(j < n)
    {
        mp[s[j]]++;                        
        maxi = max(maxi, mp[s[j]]);  

        if((j - i + 1) - maxi > k)
        {
            mp[s[i]]--;
            i++;
        }

        ans = max(ans, (j - i + 1)); 
        j++;   
    }
    return ans;
}


int main()
{
    int k = 2;
    string s = "ABABA";
    cout << solution(s, k) << endl;

    return 0;
}

Output

5