Partition String Into Substrings With Values at Most K

Partition String Into Substrings With Values at Most K - 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.
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.

Input & Output

Example 1 — Basic Case

$ Input: s = "165312", k = 60

› Output: 4

💡 Note: Optimal partition: ["16", "53", "1", "2"]. Values are [16, 53, 1, 2], all ≤ 60. Total: 4 substrings.

Example 2 — Impossible Case

$ Input: s = "238", k = 4

› Output: -1

💡 Note: Single digits "2", "3" are ≤ 4, but "8" > 4. Since we can't partition "8", no good partition exists.

Example 3 — All Single Digits

$ Input: s = "123", k = 5

› Output: 3

💡 Note: Each digit forms its own partition: ["1", "2", "3"]. Values [1, 2, 3] are all ≤ 5.

Constraints

1 ≤ s.length ≤ 10⁵
s consists only of digits from '1' to '9'
1 ≤ k ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input

String of digits and maximum value k

Process

Find optimal partition with minimum substrings

Output

Minimum number of valid substrings

Key Takeaway

🎯 Key Insight: Greedily take the longest valid substring at each step to minimize total partitions

Asked in

G Google 45 a Amazon 38 M Microsoft 25

The key insight is to use a greedy approach: at each position, take the longest possible substring whose value doesn't exceed k. This minimizes the total number of partitions. The greedy algorithm runs in O(n²) time and O(1) space, making it efficient for this problem.

Common Approaches

Approach	Time	Space	Notes
✓ Dynamic Programming	O(n²)	O(n)	Use DP to find minimum partitions by trying all valid substrings at each position
Brute Force - Try All Partitions	O(2ⁿ)	O(n)	Generate all possible partitions and find minimum valid one
Greedy - Take Longest Valid Substring	O(n²)	O(1)	At each step, take the longest possible substring that doesn't exceed k

Dynamic Programming — Algorithm Steps

Define dp[i] = min partitions for s[0:i]
For each position i, try all valid substrings ending at i
Update dp[i] = min(dp[i], dp[j] + 1) for valid s[j:i]

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

dp[0] = 0, others = infinity

Fill DP Table

For each position, try all valid endings

Result

dp[n] contains minimum partitions

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int solution(const char* s, int k) {
    int n = strlen(s);
    int* dp = malloc((n + 1) * sizeof(int));
    
    for (int i = 0; i <= n; i++) {
        dp[i] = INT_MAX;
    }
    dp[0] = 0;
    
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < i; j++) {
            char substring[20];
            strncpy(substring, s + j, i - j);
            substring[i - j] = '\0';
            int value = atoi(substring);
            
            if (value <= k && dp[j] != INT_MAX) {
                if (dp[j] + 1 < dp[i]) {
                    dp[i] = dp[j] + 1;
                }
            }
        }
    }
    
    int result = dp[n] == INT_MAX ? -1 : dp[n];
    free(dp);
    return result;
}

int main() {
    char s[1000];
    int k;
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    scanf("%d", &k);
    printf("%d\n", solution(s, k));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Nested loops: outer loop n iterations, inner loop up to n iterations per position

⚠ Quadratic Growth

Space Complexity

O(n)

DP array of size n+1 to store minimum partitions for each prefix

⚡ Linearithmic Space

28.5K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Dynamic Programming — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler