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.
This approach uses a greedy method to partition the string. We traverse the string while keeping track of seen characters in a HashSet. When a repeating character is encountered, we start a new substring. This way, we ensure that each substring contains unique characters.
We use an array seen to keep track of which characters have been encountered in the current substring. When a repeated character is found, we reset the array and increment the substring count.
Time Complexity: O(n), where n is the length of the string, as we traverse each character once.
Space Complexity: O(1), since the size of the HashSet or boolean array is constant (fixed alphabet size).
With the two-pointer technique, one pointer iterates over the string while another pointer marks the start of a current substring. If a repeat character is found, we adjust the start pointer to ensure all characters between the start and end pointers remain unique.
We maintain an array lastSeen to store the last index of each character. If a previously seen character's index is within the current substring's range, a new substring starts.
Time Complexity: O(n), bounds on string traversal.
Space Complexity: O(1), with 26 possible character slots.
According to the problem description, each substring should be as long as possible and contain unique characters. Therefore, we can greedily partition the string.
We define a binary integer mask to record the characters that have appeared in the current substring. The i-th bit of mask being 1 indicates that the i-th letter has already appeared, and 0 indicates that it has not appeared. Additionally, we need a variable ans to record the number of substrings, initially ans = 1.
Traverse each character in the string s. For each character c, convert it to an integer x between 0 and 25, then check if the x-th bit of mask is 1. If it is 1, it means the current character c is a duplicate in the current substring. In this case, increment ans by 1 and reset mask to 0. Otherwise, set the x-th bit of mask to 1. Then, update mask to the bitwise OR result of mask and 2^x.
Finally, return ans.
The time complexity is O(n), where n is the length of the string s. The space complexity is O(1).
| Approach | Complexity |
|---|---|
| Approach 1: Greedy with HashSet | Time Complexity: O(n), where n is the length of the string, as we traverse each character once. |
| Approach 2: Two-Pointer Technique | Time Complexity: O(n), bounds on string traversal. |
| Greedy | — |
| 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. |
Optimal Partition of String - Leetcode 2405 - Python • NeetCodeIO • 20,279 views views
Watch 9 more video solutions →Practice Optimal Partition of String with our built-in code editor and test cases.
Practice on FleetCode