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

Optimal Partition of String

Difficulty: Medium

Problem Description

Given a string s, partition the string into one or more substrings such that the characters in each substring are unique. That is, no letter appears in a single substring more than once. Return the minimum number of substrings in such a partition. Note that each character should belong to exactly one substring in a partition.

Key Insights

  • Each substring must contain unique characters.
  • When a character repeats, a new substring must start to maintain uniqueness.
  • The problem can be approached with a greedy strategy, where we keep track of seen characters in the current substring.

Space and Time Complexity

Time Complexity: O(n) - where n is the length of the string, as we traverse the string once. Space Complexity: O(1) - since the maximum number of unique characters (lowercase English letters) is constant (26).

Solution

To solve the problem, we can use a set to track the unique characters in the current substring. We iterate through the string character by character. If a character is already in the set, we increment our substring count and start a new substring by clearing the set. Otherwise, we add the character to the set.

Code Solutions

def min_partitions(s: str) -> int:
    seen = set()
    count = 1  # At least one substring is needed

    for char in s:
        if char in seen:
            count += 1  # Start a new substring
            seen.clear()  # Clear seen characters for the new substring
        seen.add(char)  # Add the current character to the set

    return count
← Back to All Questions