2522. Partition String Into Substrings With Values at Most K Medium

1/**
2 * [2522] Partition String Into Substrings With Values at Most K
3 *
4 * You are given a string s consisting of digits from 1 to 9 and an integer k.
5 * A partition of a string s is called good if:
6 * 
7 * 	Each digit of s is part of exactly one substring.
8 * 	The value of each substring is less than or equal to k.
9 * 
10 * Return the minimum number of substrings in a good partition of s. If no good partition of s exists, return -1.
11 * Note that:
12 * 
13 * 	The value of a string is its result when interpreted as an integer. For example, the value of "123" is 123 and the value of "1" is 1.
14 * 	A substring is a contiguous sequence of characters within a string.
15 * 
16 *  
17 * <strong class="example">Example 1:
18 * 
19 * Input: s = "165462", k = 60
20 * Output: 4
21 * 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.
22 * It can be shown that we cannot partition the string into less than 4 substrings.
23 * 
24 * <strong class="example">Example 2:
25 * 
26 * Input: s = "238182", k = 5
27 * Output: -1
28 * Explanation: There is no good partition for this string.
29 * 
30 *  
31 * Constraints:
32 * 
33 * 	1 <= s.length <= 10^5
34 * 	s[i] is a digit from '1' to '9'.
35 * 	1 <= k <= 10^9
36 * 
37 *  
38 * <style type="text/css">.spoilerbutton {display:block; border:dashed; padding: 0px 0px; margin:10px 0px; font-size:150%; font-weight: bold; color:#000000; background-color:cyan; outline:0; 
39 * }
40 * .spoiler {overflow:hidden;}
41 * .spoiler > div {-webkit-transition: all 0s ease;-moz-transition: margin 0s ease;-o-transition: all 0s ease;transition: margin 0s ease;}
42 * .spoilerbutton[value="Show Message"] + .spoiler > div {margin-top:-500%;}
43 * .spoilerbutton[value="Hide Message"] + .spoiler {padding:5px;}
44 * </style>
45 * 
46 */
47pub struct Solution {}
48
49// problem: https://leetcode.com/problems/partition-string-into-substrings-with-values-at-most-k/
50// discuss: https://leetcode.com/problems/partition-string-into-substrings-with-values-at-most-k/discuss/?currentPage=1&orderBy=most_votes&query=
51
52// submission codes start here
53
54impl Solution {
55    pub fn minimum_partition(s: String, k: i32) -> i32 {
56        0
57    }
58}
59
60// submission codes end
61
62#[cfg(test)]
63mod tests {
64    use super::*;
65
66    #[test]
67    fn test_2522() {
68    }
69}
70