{x}
blog image

Optimal Partition of String

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.

 

Example 1:

Input: s = "abacaba"
Output: 4
Explanation:
Two possible partitions are ("a","ba","cab","a") and ("ab","a","ca","ba").
It can be shown that 4 is the minimum number of substrings needed.

Example 2:

Input: s = "ssssss"
Output: 6
Explanation:
The only valid partition is ("s","s","s","s","s","s").

 

Constraints:

  • 1 <= s.length <= 105
  • s consists of only English lowercase letters.

Solution Explanation: Optimal Partition of String

This problem asks for the minimum number of substrings needed to partition a given string s such that each substring contains only unique characters. The optimal approach is a greedy algorithm.

Algorithm:

The core idea is to build substrings as long as possible while maintaining the uniqueness of characters within each substring. We iterate through the string, keeping track of characters already seen in the current substring. If we encounter a duplicate character, we start a new substring.

  1. Initialization:

    • ans: This variable counts the number of substrings (initialized to 1, as we start with at least one substring).
    • mask: This is a bitmask (integer) used to efficiently track which characters are present in the current substring. Each bit represents a character (a=0, b=1, ..., z=25). A bit set to 1 indicates the character is present.

  2. Iteration:

    • The code iterates through each character c in the input string s.
    • x = c - 'a': This converts the character to its corresponding integer index (0-25).
    • if (mask >> x) & 1: This checks if the x-th bit in mask is set. If it is, the character c is already in the current substring (duplicate).
      • ans += 1: Increment the substring count.
      • mask = 0: Reset the bitmask to start a new substring.
    • mask |= (1 << x): Set the x-th bit in mask to 1, indicating that character c is now in the current substring.

  3. Return:

    • After iterating through the entire string, ans holds the minimum number of substrings.

Time Complexity: O(n), where n is the length of the string. We iterate through the string once. The bitwise operations are constant time.

Space Complexity: O(1). We use a constant amount of extra space for the ans variable and the mask (integer). The space used does not depend on the input size.

Code Examples (with explanations):

The provided code examples in Python, Java, C++, Go, TypeScript, and Rust all implement this greedy algorithm using bit manipulation for efficient character tracking. They differ slightly in syntax but follow the same core logic.

Example (Python):

class Solution:
    def partitionString(self, s: str) -> int:
        ans, mask = 1, 0  # Initialize substring count and bitmask
        for c in s:       # Iterate through the string
            x = ord(c) - ord('a')  # Get character index (0-25)
            if (mask >> x) & 1:     # Check if character is already in mask
                ans += 1            # Start a new substring
                mask = 0            # Reset mask
            mask |= 1 << x          # Add character to mask
        return ans

The other languages use similar approaches, adapting the syntax to their respective features. The core logic (greedy algorithm and bit manipulation) remains consistent across all examples.