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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Optimal Partition of String

Number: 2487

Difficulty: Medium

Paid? No

Companies: Amazon, Microsoft, Google

Problem Description

Given a string s, partition it into one or more substrings such that the characters in each substring are unique (each character appears at most once per substring). Return the minimum number of substrings required such that every partition meets this condition.

Key Insights

  • Use a greedy approach: iterate through the string and extend the current substring until a duplicate character is encountered.
  • Use a set to keep track of characters in the current substring for quick duplicate detection.
  • When a duplicate is found, increment the partition count and start a new substring, resetting the set.
  • The problem constraints ensure that the set's size will always be limited (max 26), providing constant space for the set.

Space and Time Complexity

Time Complexity: O(n) where n is the length of the input string, as the string is traversed exactly once. Space Complexity: O(1) since the additional space (the set) holds at most 26 characters.

Solution

We use a greedy strategy combined with a set data structure to keep track of characters in the current substring. We traverse the string character by character:

  1. Add each unique character to the current set.
  2. If a character is found that is already in the set, we have reached a duplicate, so we count a partition and reset the set starting with this current character.
  3. Continue until all characters are processed, and the number of partitions is the answer.

Code Solutions

# Python solution for "Optimal Partition of String"

def partitionString(s: str) -> int:
    partitions = 1  # Start with one partition
    seen_chars = set()  # Set to track characters in the current partition
    
    # Iterate through each character in the string
    for char in s:
        if char in seen_chars:
            # Duplicate found, start a new partition
            partitions += 1
            seen_chars.clear()  # Reset the seen characters for the new partition
        seen_chars.add(char)  # Add the character to the current partition
    
    return partitions

# Example usage:
# print(partitionString("abacaba"))  # Output: 4
← Back to All Questions