Split a String Into the Max Number of Unique Substrings
Medium · Backtracking · Hash Table · String · Backtracking
Problem
Given a string s, split it into non-empty substrings whose concatenation is s and in which no substring appears twice. Return the largest number of substrings such a split can have.
A split that keeps s whole is always allowed, so the answer is at least 1.
Examples
Input: s = "abab" Output: 3
a, b, ab works; four pieces would repeat a and b.
Input: s = "zzz" Output: 2
z, zz uses different pieces, while z, z, z does not.
Input: s = "abcd" Output: 4
Every letter can be its own piece.
Constraints
- 1 <= s.length <= 16
- s contains only lowercase English letters
Approaches
- Baseline: every placement of cuts — time O(n · 2^n), space O(n)
Follow-up
Greedy (always cut the shortest new piece) fails on strings such as "wwwzfvedwfvhsww". The use cases change the rule (every piece a palindrome) and change the question (count the splits instead of maximizing).
Related problems
Start free on Cariara · Coding problems · System design studio
