Optimal Partition of String

Step 1: Make each piece as long as possible

Read the string from the left and keep adding letters to the current piece. Only start a new piece when the next letter is already in the current one.

Step 2: Why greedy is optimal

Ending a piece early never helps: a shorter piece leaves the next piece with more letters to hold, and more letters can only cause more repeats. So the longest possible first piece is always part of some best answer, and the same argument repeats for the rest of the string.

Step 3: Track the letters with a bitmask

The current piece's letters fit in one int: bit c is set if letter c is in it. Checking is used & bit, adding is used |= bit, and starting a new piece is used = 0.

s = "abacaba".

parts starts at 1 because the first letter always opens a piece.

public class OptimalPartitionOfString {

    public static int partitionString(String s) {
        int parts = 1;
        int used = 0;                         // bit c is set if letter c is in the current part
        for (char ch : s.toCharArray()) {
            int bit = 1 << (ch - 'a');
            if ((used & bit) != 0) {
                parts++;                      // the letter repeats: start a new part
                used = 0;
            }
            used |= bit;
        }
        return parts;
    }

    public static void main(String[] args) {
        System.out.println(partitionString("abacaba"));   // 4
        System.out.println(partitionString("ssssss"));    // 6
    }
}

The original implementation, OptimalPartitionOfString.java, is on GitHub.

• Time: O(n).
• Space: O(1): a single integer.

When the pieces must be different strings rather than have different letters, greedy no longer works: see Break a String Into Maximum Number of Unique Substrings.