2522. Partition String Into Substrings With Values at Most K

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.

class Solution {
    long long helper(string& s, int p, vector<long long>& dp, int k) {
        if(p == s.length()) return 0;
        if(dp[p] != -1) return dp[p];
        long long& res = dp[p] = INT_MAX;
        long long val = 0;
        for(int i = p; i < s.length() and val <= k; i++) {
            val = val * 10 + s[i] - '0';
            if(val <= k) {
                res = min(res, 1 + helper(s,i+1,dp,k));
            }
        }
        return res;
    }
public:
    int minimumPartition(string s, int k) {
        vector<long long> dp(s.length(), -1);
        long long res = helper(s,0,dp,k);
        return res > s.length() ? -1 : res;
    }
};