36. Longest Repeating Character Replacement

Topic :

hashing

Difficulty :

medium

Problem Link :

problem statement

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 operation at most k times.

Return the length of the longest substring containing the same letter you can get after performing the above operations.

Example 1:

Input: s = "ABAB", k = 2
Output: 4
Explanation: Replace the two 'A's with two 'B's or vice versa.

Example 2:

Input: s = "AABABBA", k = 1
Output: 4
Explanation: Replace the one 'A' in the middle with 'B' and form "AABBBBA".
The substring "BBBB" has the longest repeating letters, which is 4.

Constraints:

1 <= s.length <= 105
s consists of only uppercase English letters.
0 <= k <= s.length

solution

import java.io.*;
import java.util.*; 
class Longest_Repeating_Character_Replacement
{
    public static void main(String args[]){
      String s = "ABAB"; int k = 2;
      System.out.println(characterReplacement(s,k));
      }
     static boolean isValid (int left, int right,int maxFreq,int k)
    {
        int windowLength=(right-left)+1;
        int no_of_replacements=windowLength-maxFreq;
        
        if(no_of_replacements>k)
            return false;
        
        return true;
    }
    static int characterReplacement(String s, int k) {
       
        int n=s.length();
        int left=0;
        HashMap<Character,Integer> map=new HashMap<>();
        int right=0;
        int max=0;
        
        while(right<n){
            
            char currChar=s.charAt(right);
            map.put(currChar,map.getOrDefault(currChar,0)+1);
        
            while(!isValid(left,right,Collections.max(map.values()),k))
            {
               map.put(s.charAt(left),map.get(s.charAt(left))-1);
               left++;
            }
                
            max=Math.max(max,(right-left+1));  
            right++;
        }
        return max;
    }
}