Mutating counts without cleanup
Wrong move: Zero-count keys stay in map and break distinct/count constraints.
Usually fails on: Window/map size checks are consistently off by one.
Fix: Delete keys when count reaches zero.
Move from brute-force thinking to an efficient approach using hash map strategy.
Given a string s, return the maximum number of unique substrings that the given string can be split into.
You can split string s into any list of non-empty substrings, where the concatenation of the substrings forms the original string. However, you must split the substrings such that all of them are unique.
A substring is a contiguous sequence of characters within a string.
Example 1:
Input: s = "ababccc" Output: 5 Explanation: One way to split maximally is ['a', 'b', 'ab', 'c', 'cc']. Splitting like ['a', 'b', 'a', 'b', 'c', 'cc'] is not valid as you have 'a' and 'b' multiple times.
Example 2:
Input: s = "aba" Output: 2 Explanation: One way to split maximally is ['a', 'ba'].
Example 3:
Input: s = "aa" Output: 1 Explanation: It is impossible to split the string any further.
Constraints:
1 <= s.length <= 16
s contains only lower case English letters.
Problem summary: Given a string s, return the maximum number of unique substrings that the given string can be split into. You can split string s into any list of non-empty substrings, where the concatenation of the substrings forms the original string. However, you must split the substrings such that all of them are unique. A substring is a contiguous sequence of characters within a string.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Hash Map · Backtracking
"ababccc"
"aba"
"aa"
Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #1593: Split a String Into the Max Number of Unique Substrings
class Solution {
private Set<String> st = new HashSet<>();
private int ans;
private String s;
public int maxUniqueSplit(String s) {
this.s = s;
dfs(0);
return ans;
}
private void dfs(int i) {
if (st.size() + s.length() - i <= ans) {
return;
}
if (i >= s.length()) {
ans = Math.max(ans, st.size());
return;
}
for (int j = i + 1; j <= s.length(); ++j) {
String t = s.substring(i, j);
if (st.add(t)) {
dfs(j);
st.remove(t);
}
}
}
}
// Accepted solution for LeetCode #1593: Split a String Into the Max Number of Unique Substrings
func maxUniqueSplit(s string) (ans int) {
st := map[string]bool{}
n := len(s)
var dfs func(int)
dfs = func(i int) {
if len(st)+n-i <= ans {
return
}
if i >= n {
ans = max(ans, len(st))
return
}
for j := i + 1; j <= n; j++ {
if t := s[i:j]; !st[t] {
st[t] = true
dfs(j)
delete(st, t)
}
}
}
dfs(0)
return
}
# Accepted solution for LeetCode #1593: Split a String Into the Max Number of Unique Substrings
class Solution:
def maxUniqueSplit(self, s: str) -> int:
def dfs(i: int):
nonlocal ans
if len(st) + len(s) - i <= ans:
return
if i >= len(s):
ans = max(ans, len(st))
return
for j in range(i + 1, len(s) + 1):
if s[i:j] not in st:
st.add(s[i:j])
dfs(j)
st.remove(s[i:j])
ans = 0
st = set()
dfs(0)
return ans
// Accepted solution for LeetCode #1593: Split a String Into the Max Number of Unique Substrings
struct Solution;
use std::collections::HashSet;
impl Solution {
fn max_unique_split(s: String) -> i32 {
let n = s.len();
let mut visited: HashSet<String> = HashSet::new();
let mut res = 0;
Self::dfs(0, 0, &mut visited, &mut res, &s, n);
res as i32
}
fn dfs(
start: usize,
cur: usize,
visited: &mut HashSet<String>,
max: &mut usize,
s: &str,
n: usize,
) {
if start == n {
*max = (*max).max(cur);
} else {
for i in start..n {
if !visited.contains(&s[start..=i]) {
visited.insert(s[start..=i].to_string());
Self::dfs(i + 1, cur + 1, visited, max, s, n);
visited.remove(&s[start..=i]);
}
}
}
}
}
#[test]
fn test() {
let s = "ababccc".to_string();
let res = 5;
assert_eq!(Solution::max_unique_split(s), res);
let s = "aba".to_string();
let res = 2;
assert_eq!(Solution::max_unique_split(s), res);
let s = "aa".to_string();
let res = 1;
assert_eq!(Solution::max_unique_split(s), res);
}
// Accepted solution for LeetCode #1593: Split a String Into the Max Number of Unique Substrings
function maxUniqueSplit(s: string): number {
const n = s.length;
const st = new Set<string>();
let ans = 0;
const dfs = (i: number): void => {
if (st.size + n - i <= ans) {
return;
}
if (i >= n) {
ans = Math.max(ans, st.size);
return;
}
for (let j = i + 1; j <= n; ++j) {
const t = s.slice(i, j);
if (!st.has(t)) {
st.add(t);
dfs(j);
st.delete(t);
}
}
};
dfs(0);
return ans;
}
Use this to step through a reusable interview workflow for this problem.
Generate every possible combination without any filtering. At each of n positions we choose from up to n options, giving nⁿ total candidates. Each candidate takes O(n) to validate. No pruning means we waste time on clearly invalid partial solutions.
Backtracking explores a decision tree, but prunes branches that violate constraints early. Worst case is still factorial or exponential, but pruning dramatically reduces the constant factor in practice. Space is the recursion depth (usually O(n) for n-level decisions).
Review these before coding to avoid predictable interview regressions.
Wrong move: Zero-count keys stay in map and break distinct/count constraints.
Usually fails on: Window/map size checks are consistently off by one.
Fix: Delete keys when count reaches zero.
Wrong move: Mutable state leaks between branches.
Usually fails on: Later branches inherit selections from earlier branches.
Fix: Always revert state changes immediately after recursive call.