Split a String Into the Max Number of Unique Substrings

Medium
1221.

Split a String Into the Max Number of Unique Substrings

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.

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 <= 16
  • s consists of lowercase English letters
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @return {number}
 */
var maxUniqueSplit = function(s) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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 <= 16
  • s consists of lowercase English letters

Hints for Split a String Into the Max Number of Unique Substrings

  1. Hint 1

    With at most 16 characters there are at most 2^15 ways to cut the string — a search is feasible.

  2. Hint 2

    Backtrack: choose the next piece's end, skip it if that piece is already used, recurse, then un-use it.

  3. 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

  1. Recurse with start (first unused index) and count (pieces so far), sharing a set seen of used pieces.
  2. If count + (n − start) <= best, return — even one-character pieces for the rest would not improve the answer.
  3. If start == n, record best = count.
  4. Otherwise, for every end in start+1 … n: if s[start..end) is not in seen, 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