2522. Partition String Into Substrings With Values at Most K
Description
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:
- Each digit of
s
is part of exactly one substring. - The value of each substring is less than or equal to
k
.
Return the minimum number of substrings in a good partition of s
. If no good partition of s
exists, return -1
.
Note that:
- The value of a string is its result when interpreted as an integer. For example, the value of
"123"
is123
and the value of"1"
is1
. - A substring is a contiguous sequence of characters within a string.
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
Solutions
Solution 1: Memoization Search
We design a function $dfs(i)$ to represent the minimum number of partitions starting from index $i$ of string $s$. The answer is $dfs(0)$.
The calculation process of the function $dfs(i)$ is as follows:
- If $i \geq n$, it means that it has reached the end of the string, return $0$.
- Otherwise, we enumerate all substrings starting from $i$. If the value of the substring is less than or equal to $k$, then we can take the substring as a partition. Then we can get $dfs(j + 1)$, where $j$ is the end index of the substring. We take the minimum value among all possible partitions, add $1$, and that is the value of $dfs(i)$.
Finally, if $dfs(0) = \infty$, it means there is no good partition, return $-1$. Otherwise, return $dfs(0)$.
To avoid repeated calculations, we can use memoization search.
The time complexity is $O(n)$, and the space complexity is $O(n)$. Where $n$ is the length of the string $s$.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
|