Split a String Into the Max Number of Unique Substrings

medium backtracking string hash set

Problem

Given a string s, cut it into one or more non-empty pieces so that every piece appears at most once (all pieces are distinct). The pieces, read left to right, must rebuild the original string exactly. Return the maximum number of pieces such a split can contain.

Inputs = "ababccc"

Output5

One best split is ["a", "b", "ab", "c", "cc"] — five distinct pieces. You cannot reach six, because any finer split forces a repeated piece (for example a second "a" or "c").

s (string)

def max_unique_split(s):
    best = 0
    seen = set()

    def backtrack(start):
        nonlocal best
        if start == len(s):
            best = max(best, len(seen))
            return
        for end in range(start + 1, len(s) + 1):
            piece = s[start:end]
            if piece in seen:
                continue
            seen.add(piece)
            backtrack(end)
            seen.remove(piece)

    backtrack(0)
    return best

function maxUniqueSplit(s) {
  let best = 0;
  const seen = new Set();

  function backtrack(start) {
    if (start === s.length) {
      best = Math.max(best, seen.size);
      return;
    }
    for (let end = start + 1; end <= s.length; end++) {
      const piece = s.slice(start, end);
      if (seen.has(piece)) continue;
      seen.add(piece);
      backtrack(end);
      seen.delete(piece);
    }
  }

  backtrack(0);
  return best;
}

class Solution {
    private int best = 0;

    public int maxUniqueSplit(String s) {
        backtrack(s, 0, new HashSet<String>());
        return best;
    }

    private void backtrack(String s, int start, Set<String> seen) {
        if (start == s.length()) {
            best = Math.max(best, seen.size());
            return;
        }
        for (int end = start + 1; end <= s.length(); end++) {
            String piece = s.substring(start, end);
            if (seen.contains(piece)) continue;
            seen.add(piece);
            backtrack(s, end, seen);
            seen.remove(piece);
        }
    }
}

int best = 0;

void backtrack(const string& s, int start, unordered_set<string>& seen) {
    if (start == (int)s.size()) {
        best = max(best, (int)seen.size());
        return;
    }
    for (int end = start + 1; end <= (int)s.size(); end++) {
        string piece = s.substr(start, end - start);
        if (seen.count(piece)) continue;
        seen.insert(piece);
        backtrack(s, end, seen);
        seen.erase(piece);
    }
}

int maxUniqueSplit(string s) {
    best = 0;
    unordered_set<string> seen;
    backtrack(s, 0, seen);
    return best;
}

Explanation

Imagine walking through the string and, at each position, deciding where to drop the next cut. From a given start index, the next piece can be any prefix of the remaining text: one character, two characters, and so on up to the whole tail. That is exactly the kind of branching choice that backtracking handles well.

To enforce the "all pieces distinct" rule we keep a hash set called seen holding the pieces chosen so far on the current path. Before we commit to a candidate piece we check the set: if the piece is already there, skipping it prunes a dead branch immediately. Otherwise we add it, recurse from the end of that piece, and — crucially — remove it again when we return, so other branches start from a clean slate.

When start reaches the end of the string, the current path is a complete, valid split. Its size equals the number of pieces in seen, so we update best with the larger of the old best and that count.

Tracing s = "ababccc": one path takes "a", then "b", then "ab", then "c", then "cc", consuming all seven characters with five distinct pieces, so best becomes 5. Other paths either run out of fresh pieces sooner or repeat a piece (a second "a", "b", or "c"), so none beats 5 — the answer.

Because every choice is undone on the way back up, a single shared set explores the entire decision tree without leaking state between branches.

Time: O(n · 2ⁿ) Space: O(n)