Optimal Partition of String

Medium
680.

Optimal Partition of String

Optimal Partition of String is a medium coding problem on strings, hash table and greedy, asked in Amazon, Google and Zomato interviews.

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.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @return {number}
 */
var partitionString = function(s) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Optimal Partition of String — Solution in Python, Java & C++

Optimal Partition of String solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Optimal Partition of String is a medium coding problem on strings, hash table and greedy, asked in Amazon, Google and Zomato interviews.

  • Difficulty: Medium
  • Topics: Strings, Hash Table, Greedy
  • Asked at: Amazon, Google, Zomato
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

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.

Hints for Optimal Partition of String

  1. Hint 1

    Extend the current piece as far as possible; cut only when forced.

  2. Hint 2

    You are forced exactly when the next character already appears in the current piece.

  3. Hint 3

    A 26-bit mask tracks the current piece's characters in O(1) per step.

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

Java

public static int partitionString(String s) {
    int seen = 0, parts = 1;
    for (int i = 0; i < s.length(); i++) {
        int bit = 1 << (s.charAt(i) - 'a');
        if ((seen & bit) != 0) { parts++; seen = 0; }
        seen |= bit;
    }
    return parts;
}

C++

int partitionString(string s) {
    int seen = 0, parts = 1;
    for (char c : s) {
        int bit = 1 << (c - 'a');
        if (seen & bit) { parts++; 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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Hashing: Hash Maps and Hash Sets