Skip to main content
Talentd

Partition String Into Substrings With Values at Most K - Solution & Explanation

MediumStringDynamic ProgrammingGreedy12 min read
Practice this problem

Problem Statement

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

 

Approach Overview

Problem Overview: You are given a numeric string s and an integer k. Split the string into the minimum number of contiguous substrings such that every substring, when interpreted as an integer, is less than or equal to k. If any single digit already exceeds k, the partition is impossible.

Approach 1: Greedy Expansion (O(n) time, O(1) space)

The optimal strategy is greedy. Scan the string from left to right and build the current number digit by digit. Each step multiplies the current value by 10 and adds the next digit. If the value becomes greater than k, you start a new partition at that digit and reset the current value. This works because extending a substring as long as it stays ≤ k always minimizes the total number of partitions. The algorithm performs a single pass over the string, making it linear time. This approach relies on simple numeric accumulation and is a classic greedy pattern often seen in Greedy and String problems.

Approach 2: Dynamic Programming (O(n * d) time, O(n) space)

A Dynamic Programming solution considers all valid substring endings. Let dp[i] represent the minimum partitions needed for the prefix ending at index i. For each index, expand backward while constructing the numeric value of s[j..i]. If the value is ≤ k, update dp[i] = min(dp[i], dp[j-1] + 1). The backward expansion stops once the number exceeds k. Since the number of digits in k limits the substring length, each state checks only a small window of characters. This approach is more flexible if the problem later introduces additional constraints or scoring rules.

Recommended for interviews: The greedy scan is the expected solution. It runs in O(n) time with constant space and demonstrates that you recognize the monotonic property of the substring value as digits are appended. Showing the DP formulation first can demonstrate deeper reasoning, but implementing the greedy approach proves you can simplify the problem to its optimal form.

Approach 1: Greedy Approach

The idea is to partition the string greedily by always taking the longest possible substring that can form according to the constraint (value ≤ k). Start with the first character, keep extending the substring until adding another digit creates a number greater than k. If at any character, the digit itself is already greater than k, return -1, as it's impossible to form a valid substring starting at that position.

We iterate over 's' and at each step, try to form the largest possible substring from the current position that doesn't exceed 'k'. We increment the count for each newly formed substring, and move the index to the start of the next potential substring.

Code

PythonJavaScript

Python

JavaScript

Complexity

Time Complexity: O(n), where n is the length of the string 's'.
Space Complexity: O(1), since no extra data structures are used apart from variables for counting and indexing.

Try this approach in the editor →

Approach 2: Dynamic Programming Approach

Use dynamic programming to solve the problem by maintaining a dp array where dp[i] represents the minimum number of partitions required for the substring s[0:i+1]. For each i, attempt substrings ending at i and start with j (where j < i) such that the substring value doesn't exceed k. Transition dp[i] by minimizing over previous positions.

The code initializes a dp array where each position is set to a high number (INT_MAX) except for dp[0], which starts at 0. For each position `i`, it calculates potential substrings that end at `i` by iterating backwards. It updates dp[i] if the current number is within k range and the subproblem dp[j-1] is not overflown. Finally, it checks if dp[n] is valid for a good partition.

Code

C++C#

C++

C#

Complexity

Time Complexity: O(n^2), where n is the length of the string due to the nested loop.
Space Complexity: O(n), because of the dp array used for recording minimum partitions until each position.

Try this approach in the editor →

Approach 3: Memoization Search

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.

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Greedy Approach

Time Complexity: O(n), where n is the length of the string 's'.
Space Complexity: O(1), since no extra data structures are used apart from variables for counting and indexing.

Dynamic Programming Approach

Time Complexity: O(n^2), where n is the length of the string due to the nested loop.
Space Complexity: O(n), because of the dp array used for recording minimum partitions until each position.

Memoization Search—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Greedy ExpansionO(n)O(1)Best choice for the original problem. Single pass with minimal memory.
Dynamic ProgrammingO(n * d)O(n)Useful when exploring variations or when greedy correctness is unclear.

Video Solution

2522. Partition String Into Substrings With Values at Most K Hindi • ThinkCode • 781 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Partition String Into Substrings With Values at Most K easy or hard?
The problem is classified as Medium on LeetCode. The implementation is straightforward once the greedy insight is recognized, but identifying that extending the substring as long as it stays ≤ k minimizes partitions requires algorithmic intuition.
Partition String Into Substrings With Values at Most K Python/Java solution
Most implementations follow the same greedy logic across languages. Maintain a running number, append digits while the value stays ≤ k, and split when it exceeds k. The approach works efficiently in Python, JavaScript, C++, or C# with linear time complexity.
How to solve Partition String Into Substrings With Values at Most K in O(n)?
Scan the string from left to right and keep building the current number using current = current * 10 + digit. If the value exceeds k, increment the partition count and start a new substring from the current digit. If a single digit is already greater than k, the problem has no valid solution.
What is the best approach for Partition String Into Substrings With Values at Most K?
The greedy approach is the most efficient solution. Iterate through the string while forming the current numeric value and start a new substring whenever the value exceeds k. This guarantees the minimum number of partitions and runs in O(n) time with O(1) space.
Is Partition String Into Substrings With Values at Most K asked at Google/Amazon/Meta?
Problems combining greedy decisions with numeric string parsing commonly appear in interviews at companies like Amazon, Google, and Meta. Variations may involve minimizing partitions, validating substring ranges, or working with numeric constraints in strings.
What data structure is used in Partition String Into Substrings With Values at Most K?
The greedy solution does not require complex data structures. It uses simple integer accumulation while scanning a string. The alternative dynamic programming approach uses an array dp[] to store the minimum partitions for each prefix.
What is the time complexity of Partition String Into Substrings With Values at Most K?
The optimal greedy solution runs in O(n) time where n is the length of the string, since each digit is processed once. Space complexity is O(1) because only a running numeric value and a counter are maintained.

Ready to solve this problem?

Practice Partition String Into Substrings With Values at Most K with our built-in code editor and test cases.

Practice on FleetCode
Previous

Longest Substring Without Repeating Characters

Next

Longest Palindromic Substring