Longest Repeating Character Replacement

Given a string s that consists of only uppercase English letters, you can perform at most k operations on that string. In one operation, you can choose any character of the string and change it to any other uppercase English character.

Find the length of the longest sub-string containing all repeating letters you can get after performing the above operations

Example Test Case

Input: s = “ABABAABA”, k = 2

Output: 6

Explanation:
Replace the two ‘B’s with two ‘A’s.

Brute Force Solution

Let’s call a substring of the original string which can be converted into a substring of repeated characters as homogeneous substring. Also for any substring, let us call the character which is occurring most number of times as the majority character.

To convert a substring to a homogeneous substring with minimum number of character replacements, we need to change all non majority character to the majority character. for example, if my substring is “ABCBBB” , the majority character is “B”. Now, to convert it into homogeneous substring, the number of replacements it would take to convert the substring to a homogeneous substring will be exactly equal to no of non-majority characters.

For the above substring, the number would be 2 (replacing A and C by B). Therefore, if the number of non majority characters is more than k , then we can never convert the substring to a homogeneous substring. We can implement the above solution in O(n^2) time complexity.

Optimized Solution

To optimize the above solution, we can use the sliding window technique. This is because if any substring s[i...j]is non homogeneous then any substring s[i...k] cannot be homogeneous where k > j.

See the code below for implementation.

Solution Implementation

• Java

class Solution {
    public int characterReplacement(String s, int k) {
        int len = s.length();
        int[] count = new int[26];
        int start = 0;
        int maxCount = 0;
        int maxLength = 0;
        for (int end = 0; end < len; end++) {
            maxCount = Math.max(maxCount, ++count[s.charAt(end) - 'A']);
            while (end - start + 1 - maxCount > k) {
                count[s.charAt(start) - 'A']--;
                start++;
            }
            maxLength = Math.max(maxLength, end - start + 1);
        }
        return maxLength;
    }
}

Complexity Analysis:

• Time Complexity: O(N)
• Space Complexity: O(1)

function characterReplacement(s, k) {
  const len = s.length;
  const count = new Array(26).fill(0);
  let start = 0;
  let maxCount = 0;
  let maxLength = 0;

  for (let end = 0; end < len; end++) {
    maxCount = Math.max(maxCount, ++count[s.charCodeAt(end) - 'A'.charCodeAt(0)]);
    while (end - start + 1 - maxCount > k) {
      count[s.charCodeAt(start) - 'A'.charCodeAt(0)]--;
      start++;
    }
    maxLength = Math.max(maxLength, end - start + 1);
  }

  return maxLength;
}