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 <= 100000s consists of lowercase English letters.
Hints for Optimal Partition of String
Hint 1
Extend the current piece as far as possible; cut only when forced.
Hint 2
You are forced exactly when the next character already appears in the current piece.
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
- Keep a 26-bit mask of the characters in the current piece and a counter starting at 1.
- For each character, if its bit is already set, close the piece — increment the counter and reset the mask to empty.
- 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 partsJava
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