# 1.6 Longest Substring with Same Letters after Replacement (hard)

**Problem:**

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

**Intution:**

The question asks to find the longest substring that contains the same characters. It also says that we can change k characters to make a substring longer and valid.

Ex:

```
"ABAB" k = 1
```

Here we know that we can change 1 character to make a substring that is a valid answer\
AKA: a substring with all the same characters.

So a valid substring answer would be s.substring(0, 3) -> "ABA" because with can replace 1 character.

Another answer could be "BAB".

Using the sliding window technique, we set up pointers `left = 0` and `right = 0`\
We know that a our current window / substring is valid when the number of characters that need to be replaced is <= k.

Lets take the example below to understand it better:\
Ex:

```
"AABABCC" k = 2
left = 0
right = 4 inclusive
```

This is example above shows a valid substring window because we have enough k changes to change the B's to A's and match the rest of the string.

"AABAB" with 2 changes is valid

We will need to know how many letters in our substring that we need to replace.\
To find out the `lettersToReplace = (end - start + 1) - mostFreqLetter;`\
Pretty much you take the size of the window minus the most freq letter that is in the current window.

Now that we know how many characters that need to be replaced in our window, we can deduce that if `lettersToReplace > k` than the window is invalid and we decrease the window size from the left.

Pulling the whole algorithm together we get:

```java
class Solution {
    public int characterReplacement(String s, int k) {
        int[] freq = new int[26];
        int mostFreqLetter = 0;
        int left = 0;
        int max = 0;
        
        for(int right = 0; right < s.length(); right++){
            freq[s.charAt(right) - 'A']++;
            mostFreqLetter = Math.max(mostFreqLetter, freq[s.charAt(right) - 'A']);
            
            int lettersToChange = (right - left + 1) - mostFreqLetter;
            if(lettersToChange > k){
                freq[s.charAt(left) - 'A']--;
                left++;
            }
            
            max = Math.max(max, right - left + 1);
        }
        
        return max;
    }
}
```

`Time Complexity: O(N)`\
`Space Complexity: O(26) = O(1)`

Credits: <https://leetcode.com/doej4566>


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://dvpr.gitbook.io/coding-interview-patterns/1.-pattern-sliding-window/1.6-longest-substring-with-same-letters-after-replacement-hard.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.