Partition String Into Substrings With Values at Most K

Problem Description

Given a string s that consists of digits ('1' to '9') and an integer k, the goal is to partition s into substrings such that:

• Every digit from s is included in exactly one substring.
• The numerical value of each substring is less than or equal to k. Return the minimum number of substrings needed for such a partition. If no valid partition exists, return -1.

Key Insights

• The problem can be approached using dynamic programming from the end of the string towards the beginning.
• Define dp[i] as the minimum number of substrings needed for s[i:].
• Iteratively build the number from the current index and break early if the value exceeds k.
• Use a greedy inner loop to extend the substring while keeping its value valid.
• The transition is dp[i] = min(1 + dp[j+1]) over all valid j such that the value formed from s[i] to s[j] is <= k.
• If no valid partition is possible, dp[i] remains an infinite (or sentinel) value and the result is -1.

Space and Time Complexity

Time Complexity: O(n * L), where n is the length of s and L is the maximum length of a valid substring (roughly the number of digits in k, i.e., log10(k)). Space Complexity: O(n) for storing the dp array.

Solution

The solution uses dynamic programming:

1. Initialize a dp array of size n+1 with a large value (representing infinity). Set dp[n] = 0 as the base case.
2. Iterate from i = n-1 to 0. For each index, build the number by appending digits from s until the number exceeds k.
3. Update dp[i] as the minimum value of (1 + dp[j+1]) for every valid substring from index i to j.
4. Return dp[0] if a valid partition exists; otherwise, return -1.

Code Solutions