Optimal Partition of String — Medium Problem & Solution

Problem statement

Partition s into the fewest possible contiguous substrings such that no substring contains a repeated character.

Return the number of substrings in the partition.

Example 1

Input: s = "abacaba"
Output: 4
Explanation: One optimal partition is "ab", "ac", "ab", "a".

Example 2

Input: s = "ssssss"
Output: 6
Explanation: Every character must start its own substring.

Example 3

Input: s = "codekairo"
Output: 2
Explanation: "codekair" then "o".

Constraints

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

How to solve Optimal Partition of String

Greedy is optimal here: never cut early. Keep extending the current substring and start a new one only at the first character that would repeat.

Approach

1. Keep a 26-bit mask of the characters in the current piece and a counter starting at 1.
2. For each character, if its bit is already set, close the piece — increment the counter and reset the mask to empty.
3. Set the character's bit and continue.

Why it works

Exchange argument: take any optimal partition and compare it with the greedy one left to right. The greedy piece always reaches at least as far as the optimal piece starting at the same index, because it only stops when any valid piece would have to stop. So greedy uses no more pieces than optimal.

Complexity

• Time — O(n)
• Space — O(1)

Pitfalls

• Resetting the mask to the current character's bit rather than to empty and then setting it is the same thing — but resetting to empty and forgetting to set it drops that character from the new piece.
• Starting the counter at 0 undercounts by one for any non-empty string.

Reference solution

Python

def partitionString(s: str) -> int:
    seen = 0
    parts = 1
    for ch in s:
        bit = 1 << (ord(ch) - 97)
        if seen & bit:
            parts += 1
            seen = 0
        seen |= bit
    return parts

JavaScript

var partitionString = function(s) {
    var seen = 0, parts = 1;
    for (var i = 0; i < s.length; i++) {
        var bit = 1 << (s.charCodeAt(i) - 97);
        if ((seen & bit) !== 0) { parts++; seen = 0; }
        seen |= bit;
    }
    return parts;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More strings problems

• Count Number of Texts Medium
• Construct String With Repeat Limit Medium
• Minimum Number of Steps to Make Two Strings Anagram II Medium
• Count Vowel Substrings of a String Medium
• Minimum Length of String After Operations Medium
• Sum of Digit Differences of All Pairs Medium