LeetCode Entry

3003. Maximize the Number of Partitions After Operations

17.10.2025 medium 2025 kotlin

Max k-uniq parts after changing one letter

3003. Maximize the Number of Partitions After Operations medium blog post substack youtube

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/1145

Problem TLDR

Max k-uniq parts after changing one letter #hard #prefix

Intuition

Didn’t solve.

    // accca    k=2
    // 12222
    // abcca
    // 123    cca
    // acbca
    // 123    bca  bc a
    // accba
    // 1223   ba

    // 47 minutes: my algo stuck in corner cases, looking for hints
    // partition_start is not very obvious
    // 56 minute: look for solution

Precompute suffix & prefix: parts count and uniqs count so far at i. Heuristic to split into three parts: left and right parts are full and uniqs are not full. Heuristic to not split: count uniqs is less than k, so letter should go to left or right. Otherwise split once.

Approach

• prefix can be computed on the go

Complexity

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

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

Code

// 9ms
    fun maxPartitionsAfterOperations(s: String, k: Int): Int {
        val sf = Array(s.length) { IntArray(2) }
        var msk = 0; var part = 0; var res = 0
        for (i in s.lastIndex downTo 1) {
            val bit = 1 shl (s[i]-'a'); msk = msk or bit
            if (msk.countOneBits() > k) { part++; msk = bit }
            sf[i-1][0] = part; sf[i-1][1] = msk
        }
        msk = 0; part = 0
        for (i in 0..<s.lastIndex) {
            val cntall = (msk or sf[i][1]).countOneBits()
            res = max(res, part + sf[i][0] +
                if (msk.countOneBits() == k && sf[i][1].countOneBits() == k && cntall < 26) 2
                else if (min(cntall + 1, 26) <= k) 0 else 1)
            val bit = 1 shl (s[i]-'a'); msk = msk or bit
            if (msk.countOneBits() > k) { part++; msk = bit }
        }
        return res + 1
    }