LeetCode in Kotlin

3144. Minimum Substring Partition of Equal Character Frequency

Medium

Given a string s, you need to partition it into one or more balanced substrings. For example, if s == "ababcc" then ("abab", "c", "c"), ("ab", "abc", "c"), and ("ababcc") are all valid partitions, but ("a", **"bab"**, "cc"), (**"aba"**, "bc", "c"), and ("ab", **"abcc"**) are not. The unbalanced substrings are bolded.

Return the minimum number of substrings that you can partition s into.

Note: A balanced string is a string where each character in the string occurs the same number of times.

Example 1:

Input: s = “fabccddg”

Output: 3

Explanation:

We can partition the string s into 3 substrings in one of the following ways: ("fab, "ccdd", "g"), or ("fabc", "cd", "dg").

Example 2:

Input: s = “abababaccddb”

Output: 2

Explanation:

We can partition the string s into 2 substrings like so: ("abab", "abaccddb").

Constraints:

• 1 <= s.length <= 1000
• s consists only of English lowercase letters.

Solution

import kotlin.math.min

class Solution {
    fun minimumSubstringsInPartition(s: String): Int {
        val cs = s.toCharArray()
        val n = cs.size
        val dp = IntArray(n + 1)
        dp.fill(n)
        dp[0] = 0
        for (i in 1..n) {
            val count = IntArray(26)
            var distinct = 0
            var maxCount = 0
            for (j in i - 1 downTo 0) {
                val index = cs[j].code - 'a'.code
                if (++count[index] == 1) {
                    distinct++
                }
                if (count[index] > maxCount) {
                    maxCount = count[index]
                }
                if (maxCount * distinct == i - j) {
                    dp[i] = min(dp[i], (dp[j] + 1))
                }
            }
        }
        return dp[n]
    }
}

This site is open source. Improve this page.