Optimal Partition of String
MedPrompt
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 <= 105sconsists of only English lowercase letters.
Approaches
3 approaches with complexity analysis and trade-offs.
This approach uses a straightforward greedy strategy with a naive implementation for checking duplicates. The core idea is to extend the current substring as much as possible. We iterate through the string, and for each character, we check if it has already appeared in the current substring. The check is done by a nested loop that scans from the beginning of the current substring to the current position. If a duplicate is found, we end the current substring, start a new one, and increment our partition count.
Algorithm
- Initialize
partitions = 1andstartOfPartition = 0. - Iterate through the string
swith an indexifrom0tos.length() - 1. - For each character
s.charAt(i), perform a linear scan on the current substring, fromstartOfPartitiontoi-1. - Use an inner loop with index
jto check ifs.charAt(j) == s.charAt(i). - If a duplicate is found, it means the current character cannot be part of the current substring.
- Increment
partitions, and start a new substring by settingstartOfPartition = i. - Break the inner loop and continue with the next character.
- If no duplicate is found, the character is added to the current substring by simply advancing
i. - After the loop finishes, return the total
partitionscount.
Walkthrough
The algorithm maintains a pointer, startOfPartition, which marks the beginning of the current substring being formed. It then iterates through the string with a main pointer i. For each character s.charAt(i), it uses a second, inner loop to scan the slice s.substring(startOfPartition, i) to see if s.charAt(i) has appeared before. If a duplicate is encountered, a partition is made right before the current character. This means we increment the partition count and update startOfPartition to the current index i. This process continues until the entire string is traversed.
class Solution { public int partitionString(String s) { if (s == null || s.isEmpty()) { return 0; } int partitions = 1; int startOfPartition = 0; for (int i = 0; i < s.length(); i++) { char currentChar = s.charAt(i); // Linearly scan the current partition for a duplicate for (int j = startOfPartition; j < i; j++) { if (s.charAt(j) == currentChar) { // Duplicate found, start a new partition partitions++; startOfPartition = i; break; } } } return partitions; }}Complexity
Time
O(N^2), where N is the length of the string `s`. The outer loop runs N times, and the inner loop can run up to N times in the worst case (e.g., a string with no repeating characters), leading to a quadratic time complexity.
Space
O(1), as we only use a few integer variables to keep track of state (partition count and start index).
Trade-offs
Pros
Simple to understand and implement.
Uses constant extra space, O(1).
Cons
The time complexity of O(N^2) is inefficient and will likely result in a 'Time Limit Exceeded' error for larger inputs as specified in the constraints (N up to 10^5).
This approach improves upon the naive method by optimizing the duplicate-checking process. It still employs the same greedy strategy of making each substring as long as possible, but instead of a linear scan, it uses a HashSet. A HashSet provides average O(1) time complexity for checking the existence of an element. We maintain a set of characters for the current substring. When we encounter a character that's already in the set, we start a new partition.
Algorithm
- Initialize
partitions = 1. If the string is empty, return 0. - Create a
HashSet<Character>namedseento store the characters of the current substring. - Iterate through the input string
scharacter by character. - For each character
c:- Check if
cis already present in theseenset usingseen.contains(c). - If it is present, a new partition must be started. Increment
partitions, clear theseenset, and then addcto the now-empty set. - If it is not present, add
cto theseenset to extend the current substring.
- Check if
- After iterating through all characters, return the final
partitionscount.
Walkthrough
We iterate through the string once. A HashSet called seen keeps track of the unique characters in the substring we are currently building. For each character c from the input string, we check if it's in seen. If seen.contains(c) is true, it signifies the end of the current unique-character substring. We then increment our partition counter, clear the seen set completely, and add c to start the next substring. If c is not in seen, we simply add it and continue, extending the current substring.
import java.util.HashSet;import java.util.Set; class Solution { public int partitionString(String s) { if (s == null || s.isEmpty()) { return 0; } int partitions = 1; Set<Character> seen = new HashSet<>(); for (char c : s.toCharArray()) { if (seen.contains(c)) { partitions++; seen.clear(); seen.add(c); } else { seen.add(c); } } return partitions; }}Complexity
Time
O(N), where N is the length of the string. We perform a single pass through the string, and each operation on the `HashSet` (`add`, `contains`, `clear`) takes, on average, O(1) time.
Space
O(K), where K is the number of unique characters in the alphabet. Since the problem states the string consists of only lowercase English letters, K is at most 26. Therefore, the space complexity is constant, O(1).
Trade-offs
Pros
Optimal time complexity of O(N).
Relatively easy to implement and understand.
Handles the problem constraints efficiently.
Cons
While efficient, it has a slightly higher constant factor overhead compared to array-based or bitmasking solutions due to the use of a general-purpose
HashSetobject and its hashing mechanism.
This is the most optimized greedy approach, leveraging the constraint that the string only contains lowercase English letters. Instead of a HashSet or an array, we can use a single integer as a bitmask to track the characters seen in the current substring. Since there are only 26 possible characters, we can map each character to one of the first 26 bits of an integer. This method is extremely fast as bitwise operations are very low-level and efficient.
Algorithm
- Initialize
partitions = 1. If the string is empty, return 0. - Initialize an integer
mask = 0. This integer will serve as a bitmask. - Iterate through the input string
scharacter by character. - For each character
c:- Calculate the bit position corresponding to the character (e.g.,
c - 'a'). - Create a value
bitrepresenting this character's bit (e.g.,1 << (c - 'a')). - Use a bitwise AND (
&) to check if the character's bit is already set inmask. - If
(mask & bit) != 0, the character is a duplicate in the current substring. Incrementpartitionsand reset themaskto be just the current character'sbit. - If the bit is not set, use a bitwise OR (
|) to set the bit in themask:mask |= bit.
- Calculate the bit position corresponding to the character (e.g.,
- Return the final
partitionscount.
Walkthrough
The algorithm uses an integer, mask, initialized to 0. As we iterate through the string, for each character c, we determine its corresponding bit. For example, 'a' maps to bit 0, 'b' to bit 1, and so on. We check if this bit is already set in our mask using the bitwise AND operator. If it is, we've found a duplicate, so we increment the partition count and reset the mask to contain only the bit for the current character. If the bit is not set, we set it using the bitwise OR operator, effectively adding the character to our current substring's set. This avoids the overhead of data structures like HashSet and is highly performant.
class Solution { public int partitionString(String s) { if (s == null || s.isEmpty()) { return 0; } int partitions = 1; int mask = 0; // Use an integer as a bitmask for (char c : s.toCharArray()) { int bitPosition = c - 'a'; int bit = 1 << bitPosition; // Check if the bit for the current character is already set if ((mask & bit) != 0) { // Duplicate found, start a new partition partitions++; // Reset the mask for the new partition mask = bit; } else { // No duplicate, add the character to the current partition's mask mask |= bit; } } return partitions; }}Complexity
Time
O(N), where N is the length of the string. We iterate through the string once, and all bitwise operations inside the loop are executed in constant time.
Space
O(1). The space required is constant as we only use a few integer variables, regardless of the input size.
Trade-offs
Pros
Extremely fast with the best possible time complexity and very low constant factors.
Minimal space usage, requiring only a single integer for tracking.
Most efficient solution for the given constraints.
Cons
The logic might be slightly less intuitive for developers not comfortable with bitwise operations.
This approach is specifically tailored to a small, fixed character set and is less generalizable than a HashSet-based solution.
Solutions
Solution
class Solution {public int partitionString(String s) { Set<Character> ss = new HashSet<>(); int ans = 1; for (char c : s.toCharArray()) { if (ss.contains(c)) { ++ans; ss.clear(); } ss.add(c); } return ans; }}class Solution {public: int partitionString(string s) { unordered_set<char> ss; int ans = 1; for (char c : s) { if (ss.count(c)) { ++ans; ss.clear(); } ss.insert(c); } return ans; }};class Solution: def partitionString(self, s: str) -> int: ss = set() ans = 1 for c in s: if c in ss: ans += 1 ss = set() ss . add(c) return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.