Optimal Partition of String solution and explanation
IBM
Google
9 more videos on this problem
Optimal Partition of String - Leetcode 2405 - PythonNeetCodeIO · 6:48 · 21K views
Optimal Partition of String - (AMAZON) | Leetcode-2405 | Explanation ➕ Live CodingcodestorywithMIK · 15:55 · 8K views
2405. Optimal Partition of String | Leetcode Weekly Contest 310 | LeetCode 2405Bro Coders · 6:19 · 4K views
Leetcode 2405 Optimal Partition of String | Coding Decoded SDE sheetCoding Decoded · 5:05 · 1K views
Leetcode | 2405. Optimal Partition of String | Medium | Java SolutionDeveloper Docs · 7:22 · 1K views
Leetcode 2405: Optimal Partition of StringAlgorithms Casts · 9:17 · 400 views
2405. Optimal Partition of String (Leetcode Medium)Programming Live with Larry · 3:48 · 324 views
2405. Optimal Partition of String - JAVA (Detailed explanation)Sourin Majumdar · 8:11 · 317 views
LeetCode 2405 - Optimal Partition of String [Daily Challenge]Code with Carter · 5:14 · 247 views
2405. Optimal Partition of String| LeetCode Weekly Contest 310Broken Coder · 5:53 · 138 views
The problem
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.
Approach overview
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 1: Approach 1: Greedy with HashSet
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.
def min_substrings(s: str) -> int:
seen = set()
count = 0
for char in s:
if char in seen:
count += 1
seen.clear()
seen.add(char)
return count + 1
print(min_substrings("abacaba")) # Output: 4import java.util.HashSet;
public class Solution {
public int minSubstrings(String s) {
HashSet<Character> seen = new HashSet<>();
int count = 0;
for (char c : s.toCharArray()) {
if (seen.contains(c)) {
count++;
seen.clear(); // Reset
}
seen.add(c);
}
return count + 1;
}
public static void main(String[] args) {
Solution sol = new Solution();
System.out.println(sol.minSubstrings("abacaba")); // Output: 4
}
}#include <iostream>
#include <unordered_set>
using namespace std;
int minSubstrings(string s) {
unordered_set<char> seen;
int count = 0;
for (char c : s) {
if (seen.count(c)) {
count++;
seen.clear(); // Reset
}
seen.insert(c);
}
return count + 1;
}
int main() {
string s = "abacaba";
cout << minSubstrings(s) << endl; // Output: 4
return 0;
}function minSubstrings(s) {
const seen = new Set();
let count = 0;
for (const char of s) {
if (seen.has(char)) {
count++;
seen.clear();
}
seen.add(char);
}
return count + 1;
}
console.log(minSubstrings("abacaba")); // Output: 4#include <stdio.h>
#include <string.h>
#include <stdbool.h>
int minSubstrings(char *s) {
bool seen[26] = { false };
int count = 0;
for (int i = 0; s[i] != '\0'; ++i) {
if (seen[s[i] - 'a']) {
memset(seen, 0, sizeof(seen)); // Reset seen characters
count++;
}
seen[s[i] - 'a'] = true;
}
return count + 1;
}
int main() {
char s[] = "abacaba";
printf("%d\n", minSubstrings(s)); // Output: 4
return 0;
}using System;
using System.Collections.Generic;
public class Solution {
public int MinSubstrings(string s) {
HashSet<char> seen = new HashSet<char>();
int count = 0;
foreach (char c in s) {
if (seen.Contains(c)) {
count++;
seen.Clear(); // Reset
}
seen.Add(c);
}
return count + 1;
}
public static void Main() {
Solution sol = new Solution();
Console.WriteLine(sol.MinSubstrings("abacaba")); // Output: 4
}
}A set is used to track the characters in the current substring. Upon encountering a repeated character, we clear the set and begin a new substring.
Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(1), as the set's maximum size is 26.
Approach 2: Approach 2: Two-Pointer Technique
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.
def min_substrings(s):
last_seen = [-1] * 26
start = 0
count = 1
for i, char in enumerate(s):
idx = ord(char) - ord('a')
if last_seen[idx] >= start:
count += 1
start = i
last_seen[idx] = i
return count
print(min_substrings("abacaba")) # Output: 4public class Solution {
public int minSubstrings(String s) {
int[] lastSeen = new int[26];
for (int i = 0; i < 26; ++i) lastSeen[i] = -1;
int start = 0, count = 1;
for (int i = 0; i < s.length(); ++i) {
if (lastSeen[s.charAt(i) - 'a'] >= start) {
count++;
start = i;
}
lastSeen[s.charAt(i) - 'a'] = i;
}
return count;
}
public static void main(String[] args) {
Solution sol = new Solution();
System.out.println(sol.minSubstrings("abacaba")); // Output: 4
}
}#include <iostream>
#include <vector>
using namespace std;
int minSubstrings(string s) {
vector<int> lastSeen(26, -1);
int start = 0, count = 1;
for (int i = 0; i < s.length(); ++i) {
if (lastSeen[s[i] - 'a'] >= start) {
count++;
start = i;
}
lastSeen[s[i] - 'a'] = i;
}
return count;
}
int main() {
string s = "abacaba";
cout << minSubstrings(s) << endl; // Output: 4
return 0;
}function minSubstrings(s) {
const lastSeen = Array(26).fill(-1);
let start = 0;
let count = 1;
for (let i = 0; i < s.length; i++) {
const idx = s.charCodeAt(i) - 'a'.charCodeAt(0);
if (lastSeen[idx] >= start) {
count++;
start = i;
}
lastSeen[idx] = i;
}
return count;
}
console.log(minSubstrings("abacaba")); // Output: 4#include <stdio.h>
#include <string.h>
int minSubstrings(char *s) {
int lastSeen[26] = { -1 };
int start = 0, count = 1;
for (int i = 0; s[i]; ++i) {
if (lastSeen[s[i] - 'a'] >= start) {
count++;
start = i;
}
lastSeen[s[i] - 'a'] = i;
}
return count;
}
int main() {
char s[] = "abacaba";
printf("%d\n", minSubstrings(s)); // Output: 4
return 0;
}using System;
public class Solution {
public int MinSubstrings(string s) {
int[] lastSeen = new int[26];
for (int i = 0; i < 26; ++i) lastSeen[i] = -1;
int start = 0, count = 1;
for (int i = 0; i < s.Length; ++i) {
if (lastSeen[s[i] - 'a'] >= start) {
count++;
start = i;
}
lastSeen[s[i] - 'a'] = i;
}
return count;
}
public static void Main(string[] args) {
Solution sol = new Solution();
Console.WriteLine(sol.MinSubstrings("abacaba")); // Output: 4
}
}The last_seen array guides start pointers to ensure non-repeating substrings.
Time Complexity: O(n).
Space Complexity: O(1).
Approach 3: Greedy
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).
function partitionString(s: string): number {
let [ans, mask] = [1, 0];
for (const c of s) {
const x = c.charCodeAt(0) - 97;
if ((mask >> x) & 1) {
++ans;
mask = 0;
}
mask |= 1 << x;
}
return ans;
}func partitionString(s string) int {
ans, mask := 1, 0
for _, c := range s {
x := int(c - 'a')
if mask>>x&1 == 1 {
ans++
mask = 0
}
mask |= 1 << x
}
return ans
}impl Solution {
pub fn partition_string(s: String) -> i32 {
let mut ans = 1;
let mut mask = 0;
for x in s.chars().map(|c| (c as u8 - b'a') as u32) {
if mask >> x & 1 == 1 {
ans += 1;
mask = 0;
}
mask |= 1 << x;
}
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Greedy with HashSet | Time Complexity: O(n), where n is the length of the string. |
| Approach 2: Two-Pointer Technique | Time Complexity: O(n). |
| Greedy | – |
Complexity analysis
| 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. |
Frequently asked questions
Is Optimal Partition of String easy or hard?
Optimal Partition of String is categorized as a Medium difficulty problem. The implementation is straightforward once you recognize the greedy rule: start a new substring whenever a duplicate character appears.
Optimal Partition of String Python/Java solution
In Python, a set is used to store characters of the current substring while iterating through the string. In Java, a HashSet<Character> or a boolean array of size 26 is commonly used. Both implementations follow the same greedy logic and run in O(n) time.
How to solve Optimal Partition of String in O(n)?
Iterate through the string while storing characters of the current substring in a HashSet or boolean array. If the next character already exists, increment the partition counter and reset the data structure. Continue scanning until the end. Each character is handled once, giving O(n) time complexity.
What is the best approach for Optimal Partition of String?
The greedy approach using a HashSet is the most common and intuitive solution. Traverse the string once and keep track of characters in the current substring. When a duplicate character appears, increment the partition count and reset the set. This produces the minimum number of partitions in O(n) time and O(1) space.
Is Optimal Partition of String asked at Google/Amazon/Meta?
This problem follows common interview patterns around greedy string processing and hash-based duplicate detection. Variations of substring partitioning and sliding window uniqueness checks appear in interviews at companies like Amazon, Google, and Meta.
What data structure is used in Optimal Partition of String?
A HashSet or a fixed-size boolean array is typically used to track characters currently in the substring. These structures allow O(1) membership checks, which is critical for detecting duplicates efficiently while scanning the string.
What is the time complexity of Optimal Partition of String?
The optimal solution runs in O(n) time where n is the length of the string. Each character is processed exactly once and HashSet lookups take constant time on average. Space complexity is O(1) because at most 26 lowercase letters are stored.