#2522
Partition String Into Substrings With Values at Most K
specialist · 920 · lc medium +32 · verified · 47.5% accepted · 393 likes · top 32%
Description
Given a digit string s (digits 1–9) and integer k, split s into the fewest substrings such that every substring's integer value is ≤ k and every digit belongs to exactly one substring. Return the minimum number of substrings, or -1 if no valid split exists.
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.
Code
1
2
3