## 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.
``````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));
}
}``````