424. Longest Repeating Character Replacement (R)

Link: https://leetcode.com/problems/longest-substring-without-repeating-characters

Description: Given a string, find the length of the longest substring with repeating characters.

Solution:

Using a sliding window approach, we can keep track of the characters in the current substring using a frequency count. We iterate through the string and add characters to the frequency count until the window is invalid. A window is invalid if the length of the window minus the frequency of the most frequent character is greater than k. In this case, we decrease the frequency of the character at the start of the window and move the start of the window to the right. We continue this process until we reach the end of the string and keep track of the maximum length of the valid window.

When the window is invalid, we decrease the frequency of the character at the start of the window and move the start of the window to the right. This ensures that the window is valid and the length of the window is calculated correctly.

/**
 * @param {string} s
 * @param {number} k
 * @return {number}
 */
var characterReplacement = function (s, k) {
  let maxLen = 0 // This will hold the maximum length of the valid window
  let maxCount = 0 // This will hold the count of the most frequently occurring character in the current window
  let start = 0 // Start of the sliding window
  const count = {} // Character frequency count within the window

  for (let end = 0; end < s.length; end++) {
    const charEnd = s[end]
    // Update the frequency of the current character
    if (!count[charEnd]) count[charEnd] = 0
    count[charEnd]++

    // Update maxCount to the frequency of the most frequent character in the current window
    maxCount = Math.max(maxCount, count[charEnd])

    // Calculate the length of the current window
    let windowLength = end - start + 1

    // Check if the current window is valid
    if (windowLength - maxCount > k) {
      // The window is not valid, decrease the frequency of the character at 'start' and move 'start' right
      const charStart = s[start]
      count[charStart]--
      start++
    } else {
      // Update maxLen if the current window is valid and larger than previous valid windows
      maxLen = Math.max(maxLen, windowLength)
    }
  }

  return maxLen
}