Longest Repeating Character Replacement: Maximizing Repeating Sequences

The "Longest Repeating Character Replacement" problem involves finding the longest repeating character sequence in a string by replacing a limited number of characters.

Problem Statement

Given a string s and an integer k, return the length of the longest substring containing the same letter you can get after performing at most k character replacements.

Example

• Input: s = "AABABBA", k = 1
• Output: 4 (Replace the one 'B' in "AABABBA" with 'A' to get "AAAA")

Solution Approach - Sliding Window Technique (typescript)

export function characterReplacement(s: string, k: number): number {
  let count: Record<string, number> = {};
  let maxCount = 0,
    maxLength = 0,
    start = 0;

  for (let end = 0; end < s.length; end++) {
    count[s[end]] = (count[s[end]] || 0) + 1;
    maxCount = Math.max(maxCount, count[s[end]]);

    while (end - start + 1 - maxCount > k) {
      count[s[start]]--;
      start++;
    }

    maxLength = Math.max(maxLength, end - start + 1);
  }

  return maxLength;
}

Breaking Down the Solution

• Sliding Window: Maintain a window of characters using two pointers (start and end).
• Track Character Counts: Use a map to count the occurrences of each character within the window.
• Adjust Window: If the window size minus the count of the most frequent character exceeds k, shrink the window from the start.
• Calculate Max Length: Update the maximum length of the substring as the window slides.

Imagine you have a long string of colorful beads, and each bead has a letter on it. Now, your task is to make the longest string of beads where all the beads have the same letter. But, there's a catch! You can only change a few beads (let's say k beads) to match the other beads.

Here's how you can do it:

1. Start Making a Necklace: Start stringing the beads together from one end. Keep adding beads as long as they have the same letter or until you have changed k beads to match.
2. Remember the Longest Necklace: As you string the beads, remember the longest necklace you've made so far where all beads looked the same.
3. Can't Change More Beads?: If you need to change more than k beads to keep adding to your necklace, then stop. Maybe start again from a different bead.
4. Try Different Starting Points: Keep trying to start your necklace from different beads in the string, using your k chances to change beads that don't match.
5. Find the Longest Necklace: After trying different starting points and using your k chances in the best way, the longest necklace you made is your answer!

In this game, changing a bead means replacing a character in the string, and making the longest necklace of the same letter is like finding the longest substring where you can replace at most k characters to make all characters in that substring the same.

Video Explanation

Longest Repeating Character Replacement

Conclusion

The Longest Repeating Character Replacement problem is an interesting challenge that tests the sliding window technique in strings. It's a valuable exercise in balancing the frequency of characters with the allowed number of replacements.