Longest Repeating Character Replacement

Problem Statement:

In this problem, you are given a string s and an integer k. Your task is to find the length of the longest substring that contains the same character, where you can replace at most k characters in the string to form this substring.

Problem Explanation:

Given a string s, we need to determine the length of the longest substring where all characters are the same, with the possibility of replacing at most k characters in the string.

---

Approach:

The problem can be solved using the sliding window technique, where we maintain a window of characters that contains at most k different characters (the ones that we will replace). We will use the following approach:

findlength Function:

This helper function calculates the maximum length of a substring that consists entirely of the character c after replacing at most k characters in the string s.

Parameters:

• string s: The input string.
• int k: The maximum number of characters that can be replaced.
• char c: The character to form the longest substring of.

Solution Steps:

1. Initialization:

   • Start with i as the right boundary of the sliding window.
   • l is the left boundary of the sliding window.
   • cnt counts the number of characters that need to be replaced to make the substring consist entirely of c.
   • maxlength stores the maximum length of the desired substring found so far.

2. Sliding Window Technique:

   • Iterate over the string with i as the right boundary.
   • If the character at the current position s[i] is not equal to c, increment cnt.
   • If cnt exceeds k, adjust the left boundary l until cnt is less than or equal to k.
   • Update maxlength with the length of the current valid window (i - l + 1).

3. Return the result:

   • Return the maximum length found for the character c.

---

Test Cases

Test Case 1: Standard Case

Input:
s = "ABAB", k = 2

Output:
4

Explanation:
By changing the first two 'A's or the first two 'B's, we can make the entire string consist of the same character. Thus, the maximum length of the substring is 4.

---

Test Case 2: Case with a Large k

Input:
s = "AABABBA", k = 1

Output:
4

Explanation:
By replacing the middle 'B' with an 'A', we can form the substring "AAAA" of length 4. The maximum length is 4.

---

Test Case 3: No Replacement Needed

Input:
s = "BBBB", k = 2

Output:
4

Explanation:
The entire string already consists of the same character, so no replacements are needed. The maximum length is 4.

---

Test Case 4: Large String with One Change

Input:
s = "AABACD", k = 1

Output:
3

Explanation:
By changing one 'C' to 'A', we can form the substring "AAA" of length 3. Thus, the maximum length is 3.

---

Test Case 5: Multiple Characters to Replace

Input:
s = "AABBAA", k = 2

Output:
4

Explanation:
By changing the first two 'B's to 'A', we can form the substring "AAAA" of length 4. The maximum length is 4.

---

— Written by Saurabh Patil • B.Tech CSE • Software Developer