We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Partition String Into Substrings With Values at Most K

Difficulty: Medium

Problem Description

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 and 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.

Key Insights

  • Each substring must have a value that does not exceed the integer k.
  • The value of a substring is determined by interpreting the string as an integer.
  • If any single digit in the string is greater than k, it is impossible to create a good partition.
  • The goal is to find the minimum number of contiguous substrings that satisfy the above conditions.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

The problem can be approached using a greedy algorithm. We can iterate through the string while keeping track of the current substring's value. If adding a new digit to the current substring exceeds k, we finalize the current substring and start a new substring. If any single digit is greater than k, we return -1 immediately. This algorithm runs in linear time, as we only traverse the string once, and uses constant space for tracking the current substring value.

Code Solutions

def partitionString(s: str, k: int) -> int:
    n = len(s)
    current_value = 0
    count = 0
    
    for i in range(n):
        digit = int(s[i])
        
        if digit > k:
            return -1  # No valid partition possible
        
        # Check if adding this digit exceeds k
        if current_value + digit > k:
            count += 1  # Finalize the current substring
            current_value = digit  # Start a new substring
        else:
            current_value += digit  # Continue adding to current substring
            
    return count + 1  # Add the last substring
← Back to All Questions