How to Solve Partition String Into Substrings With Values at Most K

Start by scanning the string while maintaining running substring values. Use state transition dynamic programming to track the minimum substrings required. Greedily extend substrings until exceeding k, then start a new substring to ensure correctness and efficiency.

Problem Statement

Given a string s of digits from 1 to 9 and an integer k, partition s into contiguous substrings where each substring represents an integer value less than or equal to k. Return the minimum number of substrings needed for such a valid partition.

If it is impossible to create any valid partition where all substring values are at most k, return -1. Optimize your solution using state transition dynamic programming and consider greedy extensions for efficiency.

Examples

Example 1

Input: s = "165462", k = 60

Output: 4

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

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

Solution Approach

Dynamic Programming State Definition

Define dp[i] as the minimum number of substrings to partition s[0..i]. Initialize dp[0] = 0. For each position, check all previous partition points where the substring value does not exceed k and update dp[i] accordingly.

Greedy Substring Extension

While scanning the string, extend the current substring greedily until the numeric value would exceed k. When it exceeds k, commit the previous substring and start a new one. This reduces unnecessary state checks in DP.

Efficient Value Computation

Compute substring integer values incrementally to avoid repeated parsing. Maintain a rolling number using multiplication and addition by digit, and reset when starting a new substring to keep operations within bounds.

Complexity Analysis

Time complexity is O(n) in greedy-enhanced DP, where n is the length of the string, because each character is processed once with constant work per substring check. Space complexity is O(n) for the DP array or O(1) if using only previous state tracking.

What Interviewers Usually Probe

• The interviewer may hint at using a DP array to track minimal partitions.
• Watch for questions on how to efficiently check substring numeric values against k.
• Expect prompts to optimize naive DP using greedy substring extensions.

Common Pitfalls or Variants

Common pitfalls

• Attempting to parse entire substrings repeatedly without incremental computation, causing timeouts.
• Starting new substrings too early or too late, which can overcount partitions.
• Ignoring the case when a single digit exceeds k, leading to incorrect -1 return.

Follow-up variants

• Partition string into substrings where each numeric value is at least L and at most K.
• Find the maximum number of valid substrings instead of minimum.
• Allow substrings to include leading zeros and adjust the value check accordingly.

How GhostInterview Helps

• Automatically tracks minimum substring partitions using DP and greedy approaches.
• Highlights failure points when substring values exceed k and adjusts computation accordingly.
• Provides step-by-step state transitions to ensure correct and efficient partitioning logic.

Topic Pages

• String
• Dynamic Programming
• Greedy

Related GhostInterview Pages

• LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
• Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
• How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.

FAQ

What is the main pattern used in Partition String Into Substrings With Values at Most K?

The problem primarily uses state transition dynamic programming combined with greedy substring extension to minimize the number of partitions.

How do I handle substrings that exceed the value k?

Whenever a substring value exceeds k, commit the previous substring and start a new substring; if a single digit exceeds k, return -1.

Can leading zeros affect the solution?

Since s contains digits 1-9 only, leading zeros do not appear, so the solution does not need to handle them.

What is the optimal way to compute substring values?

Compute values incrementally by multiplying the previous value by 10 and adding the new digit to avoid repeated parsing.

What are common mistakes when applying DP for this problem?

Common mistakes include over-parsing substrings, miscounting partitions, and neglecting the -1 return for impossible cases.