Skip to content

424.longest-repeating-character-replacement.md

Latest commit

 

History

History
131 lines (111 loc) · 4.91 KB

424.longest-repeating-character-replacement.md

File metadata and controls

131 lines (111 loc) · 4.91 KB

424. Longest Repeating Character Replacement

Test Cases

Normal Cases

Input: s = "abab", k = 2
Output: 4

Input: s = "aabbbb", k = 1
Output: 5

Edge / Corner Cases

  • k is zero.
Input: s = "aabccc", k = 0
Output: 3
  • Concatenated to longer substring within k times with different combinations.
Input: s = "aabbaaab", k = 2
Output: 8
Explanation: "aabbaaab" > "aabbaaab"
                ^^            ^   ^  

Input: s = "aabaaaabb", k = 2
Output: 8

Sliding Window

  • Window: the longest repeating character replacement to specific C within k times.
  • Then we can use a sliding window to find the longest substring that can be formed by replacing the characters in the window. We have A..Z 26 possible replacements. Same as 1004. Max Consecutive Ones III.
fun characterReplacement(s: String, k: Int): Int {
    var answer = 0
    for (c in 'A'..'Z') {
        answer = maxOf(answer, replacement(s, k, c))
    }
    return ans
}

private fun replacement(s: String, k: Int, c: Char): Int {
    var left = 0
    var right = 0
    var count = 0
    var result = 0
    while (right < s.length) {
        if (s[right] != c) count++
        while (count > k) {
            if (s[left] != c) count--
            left++
        }
        result = max(result, right - left + 1)
        right++
    }
    return result
}

Sliding Window (Optimized)

  • Window: the longest repeating character replacement within k times.
  • We update longestRepeatingCount so that we could know how many characters that we have to replace:
windows = [AAABC]
              ^^
longestRepeatingCount = 3
// That means that we have to replace 2 characters.

我們不需要預先知道要替換的字元是什麼，我們想盡量使用滑窗裡面最多的字元，接著只要知道要替換幾個字元就可以了。例如我知道目前滑窗出現最多的次數為 5，那我們就嘗試把其他字元都換掉 window size - 5，這樣就能夠得到最長的連續字串。過程中我們不需要知道實際上要替換的字元是什麼，只要知道要替換幾個字元就可以了。

窗口长度数L - majority元素的个数M <= K

fun characterReplacement(s: String, k: Int): Int {
    var left = 0
    var right = 0
    var longestRepeatingCount = 0
    var result = 0
    val sCount = IntArray(26)
    while (right < s.length) {
        sCount[s[right] - 'A']++
        longestRepeatingCount = maxOf(longestRepeatingCount, sCount[s[right] - 'A'])

        // If the difference between the current length and max repeated count > k, we have to shrink the window
        // Equivalent to:
        // while (right - left + 1 > longestRepeatingCount + k) {
        while (right - left + 1 - longestRepeatingCount > k) {
            sSount[s[left] - 'A']--
            left++

            // We don't have to update the max repeated count here, because when 
            // shriking the window, the count won't get larger.
            // See below
        }
        result = max(result, right - left + 1)
        right++
    }
    return result
}
  • Time Complexity: O(n).
  • Space Complexity: O(1).

Questions

  1. Why we don't have to track the longest repeating character in the window?

Here we don't track the longest repeating character, the problem asks for the length of the longest substring", we only care about the number of characters that we have to replace. So we track the frequency of each character and the maximum frequency, then the number of replacement is (window size - maximum frequency), we don't care what character it is.

k = 1
      a, a, b, b, b, b
a  0  1  2  0  0  0  0
b  0  0  0  1  2  3  4
      1  2  2  2  3  4 // The longest repeating count, it doesn't matter which longest character is.
      1  2  3  3  4  5 // The answer
            ^    // We change one `b` to `a`
               ^ // We can change `b` to `a` or `a` to `b`, doesn't matter. The answer is 3 aaa or 3 bbb.

The longestRepeatingCount may be invalid at some points, but this doesn't matter, because it was valid earlier or later in the string, and all that matters is finding the max window that occurred anywhere in the string.

  1. Why we don't have to update the longestRepeatingCount when shrinking the window?

Because the longestRepeatingCount is the maximum count of the repeating character in the window, when we shrink the window, the maximum won't get larger. So we don't have to update it.

为什么左指针移动之后不用更新结果？

这是因为，我们移动左指针的起因是之前s[j]的引入，它必然是一个非majority的字符（否则整个窗口应该会继续保持合法），而无论左指针弹出的是否majority元素，都不会得到更好的结果，最多持平，所以我们不需要更新结果。