Watch 10 video solutions for Optimal Partition of String, a medium level problem involving Hash Table, String, Greedy. This walkthrough by NeetCodeIO has 20,279 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Given a string s, partition the string into one or more substrings such that the characters in each substring are unique. That is, no letter appears in a single substring more than once.
Return the minimum number of substrings in such a partition.
Note that each character should belong to exactly one substring in a partition.
Example 1:
Input: s = "abacaba"
Output: 4
Explanation:
Two possible partitions are ("a","ba","cab","a") and ("ab","a","ca","ba").
It can be shown that 4 is the minimum number of substrings needed.
Example 2:
Input: s = "ssssss"
Output: 6
Explanation:
The only valid partition is ("s","s","s","s","s","s").
Constraints:
1 <= s.length <= 105s consists of only English lowercase letters.Problem Overview: You receive a lowercase string s. Split it into the minimum number of substrings so that each substring contains only unique characters. Every time a character repeats within the current substring, you must start a new partition.
The constraint that every substring must contain unique characters naturally pushes toward a greedy strategy. You keep extending the current substring until a duplicate character appears. At that moment, the optimal decision is to cut the partition immediately and start fresh.
Approach 1: Greedy with HashSet (O(n) time, O(1) space)
This approach scans the string once while maintaining a HashSet of characters currently in the active substring. For each character, perform a constant-time hash lookup. If the character is not present, insert it and continue expanding the substring. If the character already exists in the set, you must start a new partition: increment the partition counter, clear the set, and add the character as the first element of the new substring.
The key insight is that delaying the split cannot improve the result. Once a duplicate appears, the current substring already violates the uniqueness constraint. Cutting immediately ensures the smallest number of partitions. Because the alphabet size is limited (26 lowercase letters), the space complexity is effectively O(1). This technique relies heavily on fast membership checks using a hash table and sequential scanning of the string.
Approach 2: Two-Pointer Technique (O(n) time, O(1) space)
The two-pointer version treats each substring as a sliding window. Maintain a left pointer marking the start of the current partition and expand a right pointer while characters remain unique. Instead of a HashSet, use a fixed-size frequency array or boolean map for 26 letters. When the right pointer encounters a character already seen in the current window, finalize the partition, reset the structure, move the left pointer to the current position, and begin forming the next substring.
This method follows the same greedy logic but frames it as a window expansion problem. It works well if you are comfortable with sliding window patterns and constant-size arrays. The operations remain linear because each character is processed once.
Recommended for interviews: The greedy HashSet approach is what most interviewers expect. It clearly demonstrates understanding of greedy decisions and constant-time membership checks using a hash table. The two-pointer variant is equally optimal but mainly shows familiarity with sliding window patterns from greedy and string-processing problems.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy with HashSet | O(n) | O(1) | Best general solution. Simple implementation with constant-time duplicate checks. |
| Two-Pointer Technique | O(n) | O(1) | Useful if you prefer sliding window logic with a fixed-size frequency array. |