2522. Partition String Into Substrings With Values at Most K

Problem Description

You are tasked with partitioning a string s which is composed of digits from 1 to 9 into a set of substrings. In the process of partitioning s, there are certain constraints that define what constitutes a "good" partition:

Each digit in s can only be a part of one substring, ensuring no overlap.
Each substring, when converted to an integer, should have a value less than or equal to a given threshold k.

The goal of this exercise is to find the minimum number of substrings that can be created while maintaining a "good" partition of s. However, if it is not possible to partition s according to the criteria, you should return -1.

Note:

The conversion of a substring to its integer value must be taken into account. For instance, the substring "123" is evaluated as the integer 123.
A substring is a contiguous block of characters found within the larger string s.

Intuition

In approaching the problem, the key is to break the string s into all possible substrings that comply with the value limit set by k and then find the minimal count among those possible partitions. To accomplish this systematically, a recursive approach, also known as Depth-First Search (DFS), can be used:

Begin at the start of the string and progressively create substrates by adding one digit at a time until the value of the current substring exceeds k.
If the value does not exceed k, you recursively call the function for the rest of the string, starting just after the current substring.
Keep a global record of the least number of substrates needed to partition the string successfully.

Since this approach can result in the same substrings being evaluated multiple times, we use memoization to store the results of subproblems and avoid redundant calculations. This optimization is necessary to ensure that the solution is efficient, especially when dealing with large strings. The pythonic way to achieve memoization is using the @cache decorator, which automatically stores the results of the expensive recursive calls.

Lastly, if after applying this method the minimum count remains undefined (inf), that means no good partition can be made, hence the function should return -1.

Learn more about Greedy and Dynamic Programming patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which of the following shows the order of node visit in a Breadth-first Search?

I don’t know

Solution Approach

The implementation of the solution is based on a recursive depth-first search (DFS) approach, with memoization to improve efficiency. Here's the breakdown of its algorithm:

We define a recursive helper function dfs, which receives an index i. This function attempts to partition the string starting from i and returns the minimum number of substrings needed for a good partition from this index onward.
When dfs is called with an index i, it checks if i is equal or greater than the length of s. If true, this indicates the end of the string has been reached and no additional substrings are needed, so it returns 0.
The function initializes two variables, res and v. The former is set to infinity to simulate a maximum possible number, which is used to find the minimum count of substrings; the latter holds the current numerical value of the substring being formed.
A loop is used to try forming substrings starting from the index i. In each iteration, a digit is added to the current value v, which keeps track of the integer value of the current substring.
If adding another digit makes v greater than k, the loop breaks, as the substring is no longer valid.
If the current substring's value does not exceed k, dfs is called recursively with the index just after the current substring to compute the minimum substrings needed for the remainder of s.
The minimum value between the res and the recursive call result is taken to find the optimal number of substrings up to the current digit.
After evaluating all possibilities starting from index i, the function returns the minimum count found plus 1 to include the current substring in the total.
The outer dfs function is wrapped with the @cache decorator. This decorator ensures that the results of dfs calls for each starting index are stored and directly returned upon subsequent calls with the same index.
The dfs function is initially called with index 0 to start partitioning from the beginning of the string s. The result is checked against infinity; if it is less, that means a good partition was found, and the answer is returned. Otherwise, it means no good partition is possible and -1 is returned.

This solution takes advantage of the fact that Python has built-in support for memoization through the @cache decorator as part of the functools library, and it uses recursion to explore all possible partition strategies. This, combined with memoization, allows for a more manageable exploration of the problem space while avoiding redundant calculations.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12

1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

<=, left, right<, left, right<=, right, left<, right, left

I don’t know

Example Walkthrough

Let's walk through a simple example to illustrate the solution approach:

Imagine we have the string s = "1234" and the threshold k = 12. We want to find the minimum number of substrings we can partition s into without any of them having an integer value greater than k.

Here is how we apply the solution approach:

Call the recursive dfs function starting at index 0.
The function initializes res to infinity and v to 0.
It starts trying to form a substring by adding one character at a time, checking whether v exceeds k:
- First iteration:
  - The current value v is 0. The digit at s[0] is 1, so v=1.
  - Since v is less than k, recursively call dfs with index 1.
  - The recursive call will try all possible partitions starting from s[1].
- Second iteration:
  - Now v=1, and the next digit is 2, so v=12 (concatenating the digits 1 and 2 to form 12).
  - Since v is still less than or equal to k, recursively call dfs with index 2.
The loop will continue to add characters until the value of v exceeds k or we reach the end of the string.
When the recursive calls return, they give us the minimum number of substrings needed from that index onwards.
We compare all these returned values to find the minimum number amongst them and add 1 to include the current substring.
Once the final recursive call finishes, we check if the result is infinity. If not, we return that result, which will represent the minimum number of substrings.

Following this process for the string s = "1234" with k = 12:

dfs(0) starts, and attempts to build substrings. It sees that both dfs(1) (after using "1") and dfs(2) (after using "12") are valid paths to explore. It cannot go further to dfs(3) because 123 is greater than k.
dfs(1) will further break down the string "234", and once again, it finds that both dfs(2) (using "2") and dfs(3) (using "23") are valid. dfs(3) calls will continue until it reaches the end of the string, incrementing the substring count as needed.
dfs(2) will also try to explore, but as dfs(3) has already computed the minimum substrings from that point, it will provide the pre-computed value due to memoization.

In the end, the minimum substrings that s can be partitioned into using this approach are two: "12" and "34", both of which are less than or equal to k.

This example simplifies the process but effectively demonstrates the recursive and memoization techniques used in the solution approach.

Solution Implementation

1from functools import lru_cache
2import math
3
4class Solution:
5    def minimumPartition(self, s: str, k: int) -> int:
6        # Utility function to perform the Depth-First Search (DFS).
7        # Caches the results to avoid recalculating for the same inputs.
8        @lru_cache(maxsize=None)
9        def dfs(index):
10            # If the index is beyond the string length, no more partitions are needed.
11            if index >= string_length:
12                return 0
13          
14            # Initialize the result as infinity to find the minimum partitions.
15            # 'value' will store the numeric value generated from the string as we traverse.
16            result, value = math.inf, 0
17          
18            # Iterate through the string characters starting from the current index.
19            for j in range(index, string_length):
20                # Accumulate the numeric value by considering the current character as part of a number.
21                value = value * 10 + int(s[j])
22              
23                # If the generated value exceeds 'k', no valid partition can be made, so break out of the loop.
24                if value > k:
25                    break
26              
27                # Recursively find the minimum number of partitions needed for the remaining substring.
28                # Add 1 for the current partition and take the minimum with the current result.
29                result = min(result, dfs(j + 1))
30          
31            # Return the result of 1 (for the current partition) plus the recursively calculated partitions.
32            return result + 1
33
34        # Length of the input string.
35        string_length = len(s)
36      
37        # Start the partitioning process from the first character.
38        answer = dfs(0)
39      
40        # If the answer is infinity, no partitioning scheme is valid, so return -1.
41        # Otherwise, return the calculated minimum number of partitions.
42        return answer if answer < math.inf else -1
43

1class Solution {
2    private Integer[] memo; // memoization table for storing solutions to subproblems
3    private int strLength; // length of the input string
4    private String str; // the original input string
5    private int maxValue; // the maximum allowed value for partitioning the number
6    private final int INF = 1 << 30; // representing infinity, used for comparisons
7  
8    // Main method to calculate minimum number of splits to partition
9    public int minimumPartition(String s, int k) {
10        strLength = s.length();
11        memo = new Integer[strLength];
12        str = s;
13        maxValue = k;
14        int result = performDFS(0); // starts the depth-first search from the beginning of the string
15        return result < INF ? result : -1; // if the result is infinity, return -1, indicating it's not possible
16    }
17
18    // Helper method that uses DFS to find the minimum splits recursively
19    private int performDFS(int index) {
20        // if the current index has reached the end of the string
21        if (index >= strLength) {
22            return 0;
23        }
24        // if the current index's result is already computed, return it
25        if (memo[index] != null) {
26            return memo[index];
27        }
28        int result = INF;
29        long currentValue = 0; // to store the numeric value of the current partition
30      
31        // iterate over the string starting from the current index
32        for (int j = index; j < strLength; ++j) {
33            currentValue = currentValue * 10 + (str.charAt(j) - '0'); // build the next number by appending the current digit
34          
35            // if the currentValue exceeds the maxValue allowed for a partition, abort this loop
36            if (currentValue > maxValue) {
37                break;
38            }
39            // Recursively perform DFS for the next part and take the minimum result so far
40            result = Math.min(result, performDFS(j + 1));
41        }
42        // Add 1 for the current split and store the result in memoization table before returning
43        memo[index] = result + 1;
44        return memo[index];
45    }
46}
47

1#include <vector>
2#include <cstring>
3#include <functional>
4
5class Solution {
6public:
7    int minimumPartition(std::string s, int k) {
8        int n = s.size();
9        std::vector<int> dp(n, 0); // Create a vector for dynamic programming storage
10        memset(dp.data(), 0, sizeof(dp[0]) * n);
11        const int INF = 1 << 30; // Define an 'infinity' value for initialization
12      
13        // Define a recursive lambda function for depth-first search (memoization approach)
14        std::function<int(int)> dfs = [&](int startIndex) -> int {
15            if (startIndex >= n) return 0; // Base case: if we reach the end of string
16            if (dp[startIndex] > 0) return dp[startIndex]; // Memoization to save results
17          
18            int result = INF;
19            long currentValue = 0;
20          
21            // Try all possible partitions starting from the current index
22            for (int endIndex = startIndex; endIndex < n; ++endIndex) {
23                currentValue = currentValue * 10 + (s[endIndex] - '0'); // Calculate number value
24                if (currentValue > k) break; // If current number is bigger than k, break
25              
26                result = std::min(result, dfs(endIndex + 1)); // Recursively solve the subproblem
27            }
28          
29            return dp[startIndex] = result + 1; // Store the minimum number of partitions
30        };
31      
32        // Start the depth-first search from index 0
33        int answer = dfs(0);
34      
35        // If the answer is not updated, meaning it's not possible, return -1
36        return answer < INF ? answer : -1;
37    }
38};
39

1function minimumPartition(s: string, k: number): number {
2    const n: number = s.length;
3    const dp: number[] = new Array(n).fill(0); // Dynamic programming storage
4    const INF: number = 1 << 30; // Initialize 'infinity' value for impossible cases
5
6    // A recursive function for depth-first search with memoization
7    const dfs = (startIndex: number): number => {
8        if (startIndex >= n) return 0; // Base case: if we reach the end of the string
9
10        if (dp[startIndex] !== 0) return dp[startIndex]; // Use memoized results to save computation time
11
12        let result = INF;
13        let currentValue = 0;
14
15        // Try all possible partitions by considering the current index as the starting point
16        for (let endIndex = startIndex; endIndex < n; endIndex++) {
17            currentValue = currentValue * 10 + (s.charCodeAt(endIndex) - '0'.charCodeAt(0)); // Calculate the numeric value of the substring
18
19            if (currentValue > k) break; // Break if the current number exceeds 'k'
20
21            // Recursively solve the subproblem and update the result with the minimum partitions needed
22            result = Math.min(result, dfs(endIndex + 1));
23        }
24
25        // Store the minimum number of partitions in dp and return
26        dp[startIndex] = result + 1;
27        return dp[startIndex];
28    };
29
30    // Start the DFS from the first index
31    const answer = dfs(0);
32
33    // Return the answer if it's valid, otherwise return -1 to indicate impossibility
34    return answer < INF ? answer : -1;
35}
36
37// The types are specified based on TypeScript best practices
38// and function definition requirements. This version does not utilize classes
39// but defines methods at the global scope as requested.
40

Not Sure What to Study? Take the 2-min Quiz：

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8

1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12

1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

[30, 20, 10][100, 33, 30][10, 12, 20]

I don’t know

Time and Space Complexity

Time Complexity

The function uses a depth-first search (DFS) approach with memoization, implemented through the @cache decorator. This exploration can visit each index i at most once for each unique state, resulting in a finite number of states limited by the length n of the string s.

When we call dfs(i), in the worst case, it iterates through the rest of the string to calculate the potential partitions that do not exceed the value k. Each recursive dfs(j + 1) call attempts to partition the string at a different index j. Since v can grow up to k, once v exceeds k, the loop breaks, constraining the number of iterations.

The time complexity can be seen as O(n * t), where n is the length of the string s and t is the average number of iterations performed in the loop before v exceeds k. The average number of iterations t is difficult to precisely quantify without specific knowledge about k and the digit makeup of s, but it can be bounded by n.

Thus, the worst-case time complexity is O(n^2) as a rough estimate, although in practical scenarios it could be significantly less, depending on the nature of input s and the value of k.

Space Complexity

The space complexity of the code is driven by the recursion depth and the space needed to store the memoization states. The maximum recursion depth can be n, and the @cache decorator will store a result for each unique call to dfs(i). Since we can have at most n unique calls to the dfs function, the space complexity is O(n) because of memoization.

However, we must also consider the implicit call stack due to recursion, which adds to the space complexity. In the worst case, the call stack's maximum depth would also be n since we could be making a recursive call for every character in the string. Thus, the overall space complexity remains O(n).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

What is the best way of checking if an element exists in an unsorted array once in terms of time complexity? Select the best that applies.

Linear SearchBinary SearchQuick SelectHash Set

I don’t know

Overview

Basic Data Structures

Basic Algorithms

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Speedrun

Introduction

DFS on Tree

Binary Search Tree

Advanced

Combinatorial Search

Pruning

Additional States

Aggregation and Memoization

Dedup

Additional Practices

Speedrun

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Speedrun

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Speedrun

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Grid

Dynamic number of subproblems

Interval

Dual-Sequence

Knapsack

Bitmask

Additional Practices

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Interval

Monotonic Stack

Divide and Conquer

Line Sweep

Tree Traversal without Recursion

Greedy

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

Editorials

2522. Partition String Into Substrings With Values at Most K

Problem Description

Intuition

Solution Approach

Example Walkthrough

Solution Implementation

Time and Space Complexity

Time Complexity

Space Complexity

Recommended Readings