Skip to content

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" 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

Thinking

Split the digit string into substrings whose integer values are at most \(k\), using as few pieces as possible. Full partitions are impossible at \(n\le 10^5\), but a valid piece is at most the number of digits of \(k\) long, so each start extends only a constant number of ways.

Let \(\textit{dfs}(i)\) be the fewest pieces from index \(i\). Accumulate the value to the right, stop once it exceeds \(k\), and take \(1+\textit{dfs}(j+1)\) over legal ends. Memoization evaluates each start once; impossibility is \(\infty\), reported as \(-1\).

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
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

 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
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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;
    }
};

 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
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
}

Comments