LeetCode in Kotlin
2405. Optimal Partition of String
Medium
Given a string s, partition the string into one or more substrings such that the characters in each substring are unique. That is, no letter appears in a single substring more than once.
Return the minimum number of substrings in such a partition.
Note that each character should belong to exactly one substring in a partition.
Example 1:
Input: s = “abacaba”
Output: 4
Explanation:
Two possible partitions are (“a”,”ba”,”cab”,”a”) and (“ab”,”a”,”ca”,”ba”).
It can be shown that 4 is the minimum number of substrings needed.
Example 2:
Input: s = “ssssss”
Output: 6
Explanation:
The only valid partition is (“s”,”s”,”s”,”s”,”s”,”s”).
Constraints:
1 <= s.length <= 105sconsists of only English lowercase letters.
Solution
class Solution {
fun partitionString(s: String): Int {
var count = 1
var arr = BooleanArray(26)
for (c in s.toCharArray()) {
if (arr[c.code - 'a'.code]) {
count++
arr = BooleanArray(26)
}
arr[c.code - 'a'.code] = true
}
return count
}
}