Split a String Into the Max Number of Unique Substrings Solution
Split a String Into the Max Number of Unique Substrings solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Split a String Into the Max Number of Unique Substrings is a medium coding problem on strings, hash table and backtracking, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Strings, Hash Table, Backtracking
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Split the string s into non-empty contiguous pieces whose concatenation is s, such that no two pieces are equal. Return the largest number of pieces such a split can have.
Example 1
Input: s = "codekairo"
Output: 8
Explanation: `o` appears twice, so not every letter can stand alone — for example `c, o, d, e, k, a, i, ro`.
Example 2
Input: s = "aaaa"
Output: 2
Explanation: `a, aaa` works; three pieces would need three different lengths summing to 4, which is impossible.
Example 3
Input: s = "abab"
Output: 3
Explanation: `a, b, ab`.
Constraints
1 <= s.length <= 16s consists of lowercase English letters
Hints for Split a String Into the Max Number of Unique Substrings
Hint 1
With at most 16 characters there are at most 2^15 ways to cut the string — a search is feasible.
Hint 2
Backtrack: choose the next piece's end, skip it if that piece is already used, recurse, then un-use it.
Hint 3
Prune: if the pieces so far plus the characters left (the most pieces still possible) cannot beat the best found, stop.
How to solve Split a String Into the Max Number of Unique Substrings
Search over all cut positions with backtracking, keeping the pieces used so far in a hash set, and prune branches that cannot beat the best count.
Approach
- Recurse with
start(first unused index) andcount(pieces so far), sharing a setseenof used pieces. - If
count + (n − start) <= best, return — even one-character pieces for the rest would not improve the answer. - If
start == n, recordbest = count. - Otherwise, for every
endinstart+1 … n: ifs[start..end)is not inseen, add it, recurse with(end, count + 1), and remove it.
Why it works
Every split is a choice of the first piece followed by a split of the rest, so the recursion enumerates all splits whose pieces are distinct, and the set check rejects exactly the splits with a repeated piece. The pruning bound is valid because the remaining n − start characters can form at most that many further pieces.
Complexity
- Time —
O(2^n · n) in the worst case, far less with pruning - Space —
O(n) besides the set of current pieces
Pitfalls
- Greedily taking the shortest unused piece is not optimal in general — search is required.
- Forgetting to remove a piece from the set when backtracking.
- The pieces must be distinct as strings; equal pieces at different positions are not allowed.
Reference solution
Python
def maxUniqueSplit(s: str) -> int:
n = len(s)
seen = set()
best = [0]
def dfs(start, count):
if count + (n - start) <= best[0]:
return
if start == n:
best[0] = count
return
for end in range(start + 1, n + 1):
piece = s[start:end]
if piece in seen:
continue
seen.add(piece)
dfs(end, count + 1)
seen.remove(piece)
dfs(0, 0)
return best[0]Java
public static int maxUniqueSplit(String s) {
int[] best = new int[1];
musDfs(s, 0, 0, new HashSet<String>(), best);
return best[0];
}
static void musDfs(String s, int start, int count, Set<String> seen, int[] best) {
int n = s.length();
if (count + (n - start) <= best[0]) return;
if (start == n) {
best[0] = count;
return;
}
for (int end = start + 1; end <= n; end++) {
String piece = s.substring(start, end);
if (!seen.add(piece)) continue;
musDfs(s, end, count + 1, seen, best);
seen.remove(piece);
}
}C++
void musDfs(const string& s, int start, int count, unordered_set<string>& seen, int& best) {
int n = (int)s.size();
if (count + (n - start) <= best) return;
if (start == n) {
best = count;
return;
}
for (int end = start + 1; end <= n; end++) {
string piece = s.substr(start, end - start);
if (seen.count(piece)) continue;
seen.insert(piece);
musDfs(s, end, count + 1, seen, best);
seen.erase(piece);
}
}
int maxUniqueSplit(string s) {
unordered_set<string> seen;
int best = 0;
musDfs(s, 0, 0, seen, best);
return best;
}JavaScript
var maxUniqueSplit = function(s) {
var n = s.length, best = 0;
var seen = new Set();
var dfs = function(start, count) {
if (count + (n - start) <= best) return;
if (start === n) {
best = count;
return;
}
for (var end = start + 1; end <= n; end++) {
var piece = s.substring(start, end);
if (seen.has(piece)) continue;
seen.add(piece);
dfs(end, count + 1);
seen.delete(piece);
}
};
dfs(0, 0);
return best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Hashing: Hash Maps and Hash Sets