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 <= 105s[i] is a digit from '1' to '9'.1 <= k <= 109
class Solution {
public:
int minimumPartition(string s, int k) {
long long n = 0, res = 1;
for (int i = 0; i < s.size(); ++i) {
if (n * 10 + (s[i] - '0') > k) {
++res;
n = 0;
}
n = n * 10 + (s[i] - '0');
if (n > k)
return -1;
}
return res;
}
};