Optimal Partition of String

How it works

Since we only have 26 lowercase letters, we can represent the set of characters in the current partition using a single integer as a bitmask. Each bit position corresponds to a letter (bit 0 for 'a', bit 1 for 'b', etc.).

This is the most space-efficient approach and uses fast bitwise operations to check membership and add characters.

Steps

1. Initialize res = 1 and mask = 0.
2. For each character, compute its bit position i = char - 'a'.
3. If the bit at position i is already set in mask (i.e., mask & (1 << i) is non-zero), we have a duplicate:
   • Reset mask = 0 and increment res.
4. Set the bit for the current character: mask |= (1 << i).
5. Return res.

Complexity

• Time complexity: O(n)
• Space complexity: O(1)

Things to watch for

Starting the Result Counter at Zero

A common mistake is initializing res = 0 instead of res = 1. Since we are counting partitions and the string is non-empty, we always have at least one partition. Starting at zero would undercount by one because the final substring after the last split is never explicitly counted when we only increment on encountering duplicates.

Forgetting to Add the Character After Clearing the Set

When a duplicate is found, some implementations clear the set but forget to add the current character to the fresh set. This leads to incorrect behavior because the duplicate character that triggered the new partition should be the first character of that new partition.

Treating the Problem as Finding Unique Substrings

Some solvers confuse this with finding all unique substrings or counting unique characters globally. The goal is to partition the string such that each partition has unique characters within itself, not across the entire string. Each partition is independent and can reuse characters from previous partitions.

class Solution:
    def partitionString(self, s: str) -> int:
        res = 1
        mask = 0
        for c in s:
            i = ord(c) - ord('a')
            if mask & (1 << i):
                mask = 0
                res += 1
            mask |= (1 << i)
        return res

class Solution {
public:
    int partitionString(string s) {
        int res = 1, mask = 0;
        for (char c : s) {
            int i = c - 'a';
            if (mask & (1 << i)) {
                mask = 0;
                res++;
            }
            mask |= (1 << i);
        }
        return res;
    }
};