Partition String Into Substrings With Values at Most K — LeetCode 2522 Python Solution

The problem

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.

Example

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.

Python solution

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

Complexity

Pattern: Greedy

Take the locally best option every time — when you can prove that never costs you later. LeetCode 2522. Partition String Into Substrings With Values at Most K is filed here because LeetCode tags it Greedy, which is the vocabulary this hub collects.

The greedy guide has the Python template for the pattern and the 346 LeetCode problems that use it.

Related problems