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.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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), bounds on string traversal.
Space Complexity: O(1), with 26 possible character slots.
| 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. |
Optimal Partition of String - Leetcode 2405 - Python • NeetCodeIO • 16,684 views views
Watch 9 more video solutions →Practice Optimal Partition of String with our built-in code editor and test cases.
Practice on FleetCode