Data Structures & Algorithms in Java – Strings – Longest Repeating Character Replacement

Problem:

Given a string and a number k find the longest substring whose characters can be replaced by the most repeating character to a maximum of k times.

Example:

Given string = “ABAB” and k = 2

You can replace the substring “ABAB” with “BBBB” since the two A’s are not the most repeating character and their count is not greater than k = 2.

So the output is 4.

Similarly

Given the string AABABBA and k = 1

You can replace the substring “BABB” with “BBBB” since only one non repeating character can be replaced (k = 1) .

So the output is 4.

Try out the solution here:

https://leetcode.com/problems/longest-repeating-character-replacement/

Solution:

Hint:

• Use a sliding window , every time the number of characters within the window exceeds the given limit , slide the window by one position from the start. Return the maximum size the sliding window could expand in the process.

ALGORITHM:

STEP 1: Initialize variables to store the start and end of the sliding window , the frequency of the characters in the window , the maximum count of repeating characters in the window and the maximum size of the sliding window

STEP 2: For each character in the string,

STEP 2b: Find the frequency of the current character

STEP 2c: If frequency is greater than any other characters in the current window , choose that as the maxCount

STEP 2d: Check if the window size without the repeating characters is greater than the given limit k. If so move the start pointer of the sliding window by one position . Also reduce the count of the start character from the frequency counter since it is no longer part of the current window now

STEP 2e: Find if the current window size is greater than the previous windows , if so assign it to the maximum size

STEP 3: Return maximum size

Code:

class Solution {
    public int characterReplacement(String s, int k) {
        
        
        
        if(s.length() == 1) return 1;
        
        int start = 0;
        
        int maxCount = 0;
        
        int maxSize = 0;
        
        int freq[] = new int[26];
        
        int end = 0;
        
        for(char c: s.toCharArray()){
            
            
         int frequency =  ++ freq[c - 'A'] ;
            
            maxCount = Math.max(maxCount,frequency);
            
            
            
            if(end - start + 1 - maxCount > k){
                
                
                freq[s.charAt(start) - 'A'] --;
                
                start++;
            }
            
            
            maxSize = Math.max(maxSize,end - start +1);
            
            end++;
            
            
        }
        
        return maxSize;
        
    }
}

Let’s take the example AABABBA with replacement character limit of 2 (k =2 )

Initial window has the first character “A”

Size of the window = 1

Size of the maximum count of any character = 1

Start and end of the window points to the same character .

Current window [A]

Increment the end pointer.

Now , pick the next character “A”

Size of the maximum count of any character = 2 ( No of A = 2 )

Size of the window = 2 (start pointer points to first character , end pointer points to second character)

Number of non repeating character = (window size – maximum count ) = 2-2 = 0

This is less than the given limit k = 2, so we don’t modify the window.

Current window – [AA]

Increment the end pointer

Now pick the next character B

Size of the maximum count of any character = 2 (A = 2 , B = 1)

Number of non repeating character = (window size – maximum count) = 3 – 2 = 1

This is less than the given limit 2, so we dont modify the window

Current window – [AAB]

Increment the end pointer

Now pick the next character A

Size of the maximum count of any character = 3 ( A = 3 , B = 1)

Number of non repeating characters = (window size – maximum count ) = 4 – 3 = 1

This is less than the given limit 2 , so we don’t modify the window

Current window – [AABA]

Increment the end pointer

Now pick the next character B

Size of the maximum count of any character = 3 ( A= 3, B = 2)

Number of non repeating characters = (window size – maximum count ) = 5 – 3 = 2

This is less than the given limit 2 , so we dont modify

Current window – [AABAB]

Increment the end pointer

Now pick the next character B

Size of the maximum count of any character = 3 (A = 3 , B = 3)

Number of non repeating characters = (window size – maximum count) = 6- 3 = 3

This is greater than the given limit 2 , so we slide the start of the window by one position

We leave out the first letter

So current window – [ABABB]

Increment the end pointer

Now pick the next character A

Size of the maximum count of any character = 3 (A = 3 , B = 3)

Number of non repeating characters = (window size – maximum count) = 6 – 3 = 3

This is greater than the given limit 2 , so we slide the start of the window by one position

We leave out the first letter of the current window

So current window – [BABBA]

We have reached the end of the string now and the longest substring we have got is BABBA . The letter A in the above string can be replaced by B since it occurs only twice ( limit k = 2) so it becomes BBBBB.

The output is then 5.