# Longest Repeating Character Replacement

**1. Clarify the problem:**
Before diving into solving the problem, let's clarify the requirements:

- We are given a string consisting of uppercase English letters only.
- We can replace any character in the string with another character.
- Our goal is to find the length of the longest substring with repeating characters after performing at most
`k`

replacements.

**2. Analyze the problem:**
To solve this problem, we can use a sliding window approach. We'll maintain a window that contains the longest substring with repeating characters, and we'll update the window as we iterate through the string.

**3. Design an algorithm:**
Here is the algorithm to solve the problem:

- Initialize variables:
`max_length`

to 0 (to keep track of the maximum length of the substring).`start`

to 0 (to track the start index of the current window).`max_count`

to 0 (to track the maximum count of any character in the current window).- Create a dictionary
`char_count`

to store the count of each character in the current window.

- Iterate through the string using a variable
`end`

:- Increment the count of the current character
`s[end]`

in the`char_count`

dictionary. - Update
`max_count`

with the maximum count of any character in the current window. - If the length of the current window (end - start + 1) minus
`max_count`

is greater than`k`

, it means we need more replacements to make all characters in the window the same. In this case, we shrink the window by moving the`start`

index and decrement the count of the character at`start`

in the`char_count`

dictionary until we satisfy the condition. - Update
`max_length`

if the length of the current window is greater than`max_length`

.

- Increment the count of the current character
- Return
`max_length`

.

**4. Explain your approach:**
The approach involves using a sliding window to find the longest substring with repeating characters after performing at most `k`

replacements. We maintain a window and update it as we iterate through the string. By keeping track of the count of each character in the window and the maximum count of any character, we can determine when to shrink the window and when to update the maximum length.

**5. Write clean and readable code:**

python

```
def characterReplacement(s, k):
max_length = 0
start = 0
max_count = 0
char_count = {}
for end in range(len(s)):
char_count[s[end]] = char_count.get(s[end], 0) + 1
max_count = max(max_count, char_count[s[end]])
if (end - start + 1) - max_count > k:
char_count[s[start]] -= 1
start += 1
max_length = max(max_length, end - start + 1)
return max_length
```

**6. Test your code:**
Let's test the code with some test cases:

Test case 1:

- s = "ABAB"
- k = 2
- The expected output is 4 because we can replace two 'A's with 'B's to obtain the longest repeating substring "ABAB".

Test case 2:

- s = "AABABBA"
- k = 1
- The expected output is 4 because we can replace the first 'A' or the last 'A' with 'B' to obtain the longest repeating substring "ABBBBA".

python

```
# Test case 1
s1 = "ABAB"
k1 = 2
print(characterReplacement(s1, k1)) # Expected output: 4
# Test case 2
s2 = "AABABBA"
k2 = 1
print(characterReplacement(s2, k2)) # Expected output: 4
```

**7. Optimize if necessary:**
The sliding window approach has a time complexity of O(n) since we iterate through the string once. The space complexity is O(1) because the `char_count`

dictionary stores a maximum of 26 characters.

**8. Handle error cases:**
The code assumes that the input string `s`

is non-empty, and the value of `k`

is a non-negative integer. If the input does not satisfy these conditions, the behavior of the code may not be as expected. We can add checks at the beginning to handle these cases and return 0.

**9. Discuss complexity analysis:**
The time complexity of the solution is O(n) since we iterate through the string once. The space complexity is O(1) because the `char_count`

dictionary stores a maximum of 26 characters, which is a constant. The solution has a linear time complexity and constant space complexity.