Medium
You are given a string s
consisting of digits from 1
to 9
and an integer k
.
A partition of a string s
is called good if:
s
is part of exactly one substring.k
.Return the minimum number of substrings in a good partition of s
. If no good partition of s
exists, return -1
.
Note that:
"123"
is 123
and the value of "1"
is 1
.Example 1:
Input: s = “165462”, k = 60
Output: 4
Explanation: We can partition the string into substrings “16”, “54”, “6”, and “2”. Each substring has a value less than or equal to k = 60. It can be shown that we cannot partition the string into less than 4 substrings.
Example 2:
Input: s = “238182”, k = 5
Output: -1
Explanation: There is no good partition for this string.
Constraints:
1 <= s.length <= 105
s[i]
is a digit from '1'
to '9'
.1 <= k <= 109
class Solution {
fun minimumPartition(s: String, k: Int): Int {
if (k == 9) {
return s.length
}
var partitions = 1
var partitionValue: Long = 0
var digit: Long
for (i in 0 until s.length) {
digit = s[i].code.toLong() - '0'.code.toLong()
if (digit > k) {
return -1
}
partitionValue = partitionValue * 10 + digit
if (partitionValue > k) {
partitionValue = digit
partitions++
}
}
return partitions
}
}