## Problem Statement

Given a string with lowercase letters only. If you are allowed to replace at most `k`

letters with any letter, find the length of the longest substring having the same letters after replacement.

**Example 1:**

```
Input: s="abcababb", k=2
Output: 5
Explanation: Replace the two 'a' with 'b' in the substring 'ababb' to get the longest substring "bbbbb" with same letters.
```

**Example 2:**

```
Input: s="abccde", k=1
Output: 3
Explanation: Replace the 'b' or 'd' with 'c' to get the the longest substring "ccc" with same letters.
```

## Solution

This problem is a variant of the problem Longest Substring without repeating characters. We will use a similar **sliding-window technique** to solve this problem.

- Consider each substring as a sliding window.
- Start with a sliding window of size
`1`

(`windowStart=0, windowEnd=0`

). - Initialize a
**HashMap**that stores the character count for each character in the current window. - Iterate over the string and add one letter at a time to the window.
- We will also keep track of the letter that repeats the maximum number of times in the current window. Let’s call it
`maxRepeatLetterCount`

. - In each iteration, we know that we have a window with one letter repeating
`maxRepeatLetterCount`

times. Since we only have`k`

replacements allowed, we should keep aside the letter that repeats the most number of times and replace the remaining letters.- If the remaining letters in the window are less than or equal to
`k`

then we can replace them all. - Otherwise, we need to shrink the window as we are not allowed to replace more than
`k`

letters.

- If the remaining letters in the window are less than or equal to

```
class LongestSubstringWithSameLettersAfterReplacement {
private static int findLengthOfLongestSubstringWithSameLettersAfterReplacement(String s, int k) {
int n = s.length();
// length of the longest substring with same letters after replacement.
int maxLen = -1;
// character count for each character in the current window
Map<Character, Integer> windowCharCount = new HashMap<>();
int windowStart = 0;
for(int windowEnd = 0; windowEnd < n; windowEnd++) {
// Add the next character to the window
char c = s.charAt(windowEnd);
windowCharCount.put(c, windowCharCount.getOrDefault(c, 0) + 1);
// Calculate max repeating character in the current window
int maxRepeatLetterCount = getMaxRepeatLetterCount(windowCharCount);
/*
The current window has a letter that repeats 'maxRepeatLetterCount' times.
If the remaining letters in the window are less than or equal to k then we can replace them all.
Otherwise, we need to shrink the window since we are not allowed to replace more than 'k' letters.
*/
while(windowEnd-windowStart+1 - maxRepeatLetterCount > k) {
char leftChar = s.charAt(windowStart);
windowCharCount.put(leftChar, windowCharCount.get(leftChar) - 1);
windowStart++; // Shrink the window
}
// At this point, the number of remaining letters in the window are less than or equal to k.
// So we can replace them all to obtain a substring with same letters.
// Update the max length if the current window size is longer.
maxLen = Math.max(maxLen, windowEnd-windowStart+1);
}
return maxLen;
}
private static int getMaxRepeatLetterCount(Map<Character, Integer> charCount) {
int maxCount = 0;
for(int count: charCount.values()) {
if(maxCount < count) {
maxCount = count;
}
}
return maxCount;
}
public static void main(String[] args) {
Scanner keyboard = new Scanner(System.in);
String s = keyboard.next();
int k = keyboard.nextInt();
keyboard.close();
System.out.printf("Longest substring with same letters after replacement = %d%n", findLengthOfLongestSubstringWithSameLettersAfterReplacement(s, k));
}
}
```