LeetCode Entry

2405. Optimal Partition of String

04.04.2023 medium 2023 kotlin

use hashset, [26] array or simple 32-bit mask to store visited flags for character

2405. Optimal Partition of String medium

blog post

    var mask = 0
    fun partitionString(s: String): Int = 1 + s.count {
        val bit = 1 shl (it.toInt() - 'a'.toInt())
        (mask and bit != 0).also {
            if (it) mask = 0
            mask = mask or bit
        }
    }

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/170

Intuition

Expand all the intervals until they met a duplicate character. This will be the optimal solution, as the minimum of the intervals correlates with the maximum of each interval length.

Approach

• use hashset, [26] array or simple 32-bit mask to store visited flags for character

  Complexity

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