Partition String Into Substrings With Values at Most K

#1559 Most AskedMedium

Partition String Into Substrings With Values at Most K #1559 Most Asked

Medium

Google

8 views

Topics:

StringsGreedy Algorithms

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 <= 10⁵
s[i] is a digit from '1' to '9'.
1 <= k <= 10⁹

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the length of the input string `s` and the value of `k`? Are they within reasonable bounds, like fitting into memory?
Can the input string `s` contain any characters other than digits ('0'-'9')? What happens if it does?
If a substring's numerical value exceeds `k`, but a shorter substring starting at the same index doesn't, should I still proceed to find subsequent substrings?
If it's impossible to partition the string into substrings with values at most `k`, what should the function return? Should I return an empty array, null, or throw an exception?
Does `k` always fit in a standard integer type, or should I be concerned about potential overflow issues when converting substrings of `s` to numerical values for comparison with `k`?

Brute Force Solution

Approach

The brute force strategy is all about trying every single way to break up the big string. We explore every possible substring and check if it's valid, meaning its numerical value is not greater than the given limit.

Here's how the algorithm would work step-by-step:

Start by considering the first single character as a possible substring.
Check if the numerical value of this single character is at most the given limit.
If it is, move on. Otherwise, this is not a valid starting point.
Next, consider the first two characters as a substring.
Check if the numerical value of these two characters is at most the given limit.
If it is, move on. Otherwise, this is not a valid substring.
Continue this process, checking substrings of increasing length starting from the beginning of the string, one character at a time.
For each valid substring found, repeat the entire process starting from the character immediately after the end of that substring.
Keep track of all possible ways to partition the string into valid substrings.
From all the valid partitions, choose the one that minimizes the number of substrings used.

Code Implementation

def partition_string_brute_force(input_string, maximum_value):
    minimum_substrings = float('inf')
    best_partition = []

    def backtrack(start_index, current_partition):
        nonlocal minimum_substrings, best_partition

        if start_index == len(input_string):
            # Found a valid partition, check if it's the best one
            if len(current_partition) < minimum_substrings:
                minimum_substrings = len(current_partition)
                best_partition = current_partition[:]
            return

        for end_index in range(start_index + 1, len(input_string) + 1):
            substring = input_string[start_index:end_index]
            substring_value = int(substring)

            # Only proceed if the current substring is valid
            if substring_value <= maximum_value:

                # Explore further partitions with this substring added
                backtrack(end_index, current_partition + [substring])

    backtrack(0, [])

    return len(best_partition)

Big(O) Analysis

Time Complexity

O(n^2) – The brute force approach iterates through all possible substrings of the input string of length n. For each starting position i, it considers substrings of length 1, 2, up to n-i. This nested loop structure, where the outer loop iterates up to n and the inner loop iterates up to n-i, leads to a quadratic number of substring checks. Therefore, the time complexity involves approximately summing the series from 1 to n, which is proportional to n*(n+1)/2. Simplifying this, we get a time complexity of O(n^2).

Space Complexity

O(N) – The provided brute force approach implicitly uses recursion to explore all possible partitions of the string. In the worst-case scenario, where each single-character substring is valid, the recursion depth can reach N, where N is the length of the input string. Each recursive call adds a new frame to the call stack, leading to a maximum auxiliary space usage proportional to the depth of the recursion. Therefore, the space complexity due to the recursion stack is O(N).

Optimal Solution

Approach

The goal is to split the given string into the fewest possible parts, where the value of each part is no more than a certain limit. We want to efficiently create valid substrings from left to right, always trying to maximize the length of the current substring.

Here's how the algorithm would work step-by-step:

Start at the beginning of the string.
Try to make the biggest substring possible, making sure the value of the substring is not more than the limit.
If a single character's value is greater than the limit, immediately return that it is impossible to split the string.
Once you've made the biggest valid substring, move to the character right after the end of the substring.
Repeat the process of making the biggest valid substring until you reach the end of the string.
The total number of substrings you've created is the answer.

Code Implementation

def partition_string(input_string, maximum_value):
    number_of_substrings = 0
    string_length = len(input_string)
    start_index = 0

    while start_index < string_length:
        current_index = start_index
        current_substring_value = 0

        # Greedily expand substring.
        while current_index < string_length:
            digit = int(input_string[current_index])
            if digit > maximum_value:
                return -1

            potential_substring_value = current_substring_value * 10 + digit

            # Stop expanding substring.
            if potential_substring_value > maximum_value:
                break

            current_substring_value = potential_substring_value
            current_index += 1

        # Increment substring count.
        number_of_substrings += 1

        # Move the start index.
        start_index = current_index

    return number_of_substrings

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the string once, attempting to maximize the length of each substring. Within the loop, substring calculations happen, but each character is visited at most a constant number of times to check if it exceeds the limit or can be appended to the current substring. The overall cost is directly proportional to the number of characters n in the string since the primary operation is iterating once through the string, leading to a linear time complexity.

Space Complexity

O(1) – The algorithm primarily uses a constant number of integer variables to track the current substring and the count of substrings. The space required for these variables does not depend on the length of the input string, denoted as N. Therefore, the auxiliary space used by the algorithm is constant. This results in a space complexity of O(1).

Edge Cases

Case	How to Handle
Null or empty string input	Return an empty list or throw an IllegalArgumentException since there is no string to partition.
String with a single character and K less than the single-character value	Return an empty list because a partition is not possible.
String with a single character and K greater or equal to the single-character value	Return a list containing the single character string.
K is zero	If any character's value is greater than 0, the string cannot be partitioned, return empty list, else return a list with each character as a substring if they are all '0'.
Large K value such that single characters always fit	The result should be one character substrings and needs to scale linearly.
String with very long sequences of digits where the cumulative value exceeds integer limit	Handle potential integer overflow using long data type or BigInteger for calculations.
String contains leading zeros that could create confusion when splitting.	The algorithm needs to treat leading zeros appropriately, either removing them or accounting for them correctly in the substring value calculation.
A valid partition is not possible	Return an empty list indicating that no valid partitioning satisfies the constraint.

Null or empty string input

How to Handle:

Return an empty list or throw an IllegalArgumentException since there is no string to partition.

String with a single character and K less than the single-character value

How to Handle:

Return an empty list because a partition is not possible.

String with a single character and K greater or equal to the single-character value

How to Handle:

Return a list containing the single character string.

K is zero

How to Handle:

If any character's value is greater than 0, the string cannot be partitioned, return empty list, else return a list with each character as a substring if they are all '0'.

Large K value such that single characters always fit

How to Handle:

The result should be one character substrings and needs to scale linearly.

String with very long sequences of digits where the cumulative value exceeds integer limit

How to Handle:

Handle potential integer overflow using long data type or BigInteger for calculations.

String contains leading zeros that could create confusion when splitting.

How to Handle:

The algorithm needs to treat leading zeros appropriately, either removing them or accounting for them correctly in the substring value calculation.

A valid partition is not possible

How to Handle:

Return an empty list indicating that no valid partitioning satisfies the constraint.