1593. Split a String Into the Max Number of Unique Substrings

MediumView on LeetCode

Hash Table String Backtracking

Time: O(n * 2^n)

Space: O(n)

Intuition

Backtracking: try all ways to split the string into k unique substrings. Track used substrings in a set. Maximize k.

Algorithm

1DFS: at each position, try all prefix lengths. If prefix not in used set, add to used, recurse, remove.
2Return maximum splits found.

Common Pitfalls

•Pruning: if remaining characters < remaining needed splits, prune. Use backtracking with pruning.

1593.cs

// Approach: DFS backtracking trying all prefix splits while maintaining a seen set of used substrings.
// Time: O(n * 2^n) Space: O(n)

public class Solution
{
    private int ans = 0;
    public int MaxUniqueSplit(string s)
    {
        Dfs(s, 0, new HashSet<string>());
        return ans;
    }

    private void Dfs(string s, int start, HashSet<string> seen)
    {
        if (start == s.Length)
        {
            ans = Math.Max(ans, seen.Count);
            return;
        }

        for (int i = start + 1; i <= s.Length; ++i)
        {
            string cand = s.Substring(start, i - start);
            if (seen.Contains(cand))
                continue;
            seen.Add(cand);
            Dfs(s, i, seen);
            seen.Remove(cand);
        }
    }
}

Was this solution helpful?