Split a string into the max number of unique substrings

Hash Table String Backtracking

68.6% acceptance

Feb 25, 2026

1512

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.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn max_unique_split(s: String) -> i32 {
    let s: Vec<char> = s.chars().collect();
    let _n = s.len();
    let mut best = 1;
    let mut seen = std::collections::HashSet::new();

    fn backtrack(
      s: &[char],
      start: usize,
      seen: &mut std::collections::HashSet<String>,
      count: i32,
      best: &mut i32,
    ) {
      if start == s.len() {
        *best = (*best).max(count);
        return;
      }
      // Pruning: even if remaining chars each form unique 1-char substrings, can't beat best?
      let remaining = s.len() - start;
      if count + remaining as i32 <= *best {
        return;
      }
      for end in start + 1..=s.len() {
        let sub: String = s[start..end].iter().collect();
        if !seen.contains(&sub) {
          seen.insert(sub.clone());
          backtrack(s, end, seen, count + 1, best);
          seen.remove(&sub);
        }
      }
    }

    backtrack(&s, 0, &mut seen, 0, &mut best);
    best
  }
}