LeetCode Entry

2024. Maximize the Confusion of an Exam

7.07.2023 medium 2023 kotlin

Max same letter subarray replacing k letters

2024. Maximize the Confusion of an Exam medium blog post substack image.png

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/268

Problem TLDR

Max same letter subarray replacing k letters

Intuition

An important example is ftftftft k=3: we must fill all the intervals. It also tells, after each filling up we must decrease k. Let’s count T and F. Sliding window is valid when tt <= k || ff <= k.

Approach

We can save some lines using Kotlin collections API

Complexity

  • Time complexity: \(O(n)\)

  • Space complexity: \(O(n)\), or \(O(1)\) using asSequence

Code


fun maxConsecutiveAnswers(answerKey: String, k: Int): Int {
    var tt = 0
    var ff = 0
    var lo = 0
    return answerKey.mapIndexed { i, c ->
        if (c == 'T') tt++ else ff++
        while (tt > k && ff > k && lo < i)
        if (answerKey[lo++] == 'T') tt-- else ff--
        i - lo + 1
    }.max() ?: 0
}