Back to solutions

Optimal Partition of String

MediumArrays

Minimum substrings so each has all distinct characters.

Open problem
Constraints
  • 1 <= length <= 10^5
  • lowercase English letters

Greedy extend until repeat

Time O(n)Space O(1) (26 letters)

Grow the current piece one character at a time, tracking the set of letters in it. The instant a character would repeat, close the piece and start a new one containing that character. Extending greedily is optimal because cutting earlier could only need more pieces.

Key terms
partition:
A split of the string into consecutive non-overlapping pieces.
bitmask set:
Representing the 26 possible letters as bits of an integer for fast membership.
int partitionString(const string& s) {
    int count = 1, seen = 0;
    for (char c : s) {
        int bit = 1 << (c - 'a');
        if (seen & bit) { count++; seen = 0; }
        seen |= bit;
    }
    return count;
}
Step by step
  1. Start with one piece and an empty set of seen letters.
  2. For each character, if it is already in the current piece, increment the count and reset the set.
  3. Add the character to the (possibly reset) set.
  4. Return the total number of pieces.