LeetCode 2522. Partition String Into Substrings With Values at Most K Solution in Java, C++, Python & Go | Explanation + Code

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" is 123 and the value of "1" is 1.
• 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 ≥ 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) = ∞, 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.

PythonJavaC++Go

class Solution: def minimumPartition(self, s: str, k: int) -> int: @cache def dfs(i): if i >= n: return 0 res, v = inf, 0 for j in range(i, n): v = v * 10 + int(s[j]) if v > k: break res = min(res, dfs(j + 1)) return res + 1 n = len(s) ans = dfs(0) return ans if ans < inf else -1(code-box)

class Solution { private Integer[] f; private int n; private String s; private int k; private int inf = 1 << 30; public int minimumPartition(String s, int k) { n = s.length(); f = new Integer[n]; this.s = s; this.k = k; int ans = dfs(0); return ans < inf ? ans : -1; } private int dfs(int i) { if (i >= n) { return 0; } if (f[i] != null) { return f[i]; } int res = inf; long v = 0; for (int j = i; j < n; ++j) { v = v * 10 + (s.charAt(j) - '0'); if (v > k) { break; } res = Math.min(res, dfs(j + 1)); } return f[i] = res + 1; } }(code-box)

class Solution { public: int minimumPartition(string s, int k) { int n = s.size(); int f[n]; memset(f, 0, sizeof f); const int inf = 1 << 30; function<int(int)> dfs = [&](int i) -> int { if (i >= n) return 0; if (f[i]) return f[i]; int res = inf; long v = 0; for (int j = i; j < n; ++j) { v = v * 10 + (s[j] - '0'); if (v > k) break; res = min(res, dfs(j + 1)); } return f[i] = res + 1; }; int ans = dfs(0); return ans < inf ? ans : -1; } };(code-box)

func minimumPartition(s string, k int) int { n := len(s) f := make([]int, n) const inf int = 1 << 30 var dfs func(int) int dfs = func(i int) int { if i >= n { return 0 } if f[i] > 0 { return f[i] } res, v := inf, 0 for j := i; j < n; j++ { v = v*10 + int(s[j]-'0') if v > k { break } res = min(res, dfs(j+1)) } f[i] = res + 1 return f[i] } ans := dfs(0) if ans < inf { return ans } return -1 }(code-box)