## 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.

## Leave a Reply