Maximum Unique String Split

1. Step 1: Initialize Solution.maxUniqueSplit

   Replace the empty starter with the first real state owned by Solution.maxUniqueSplit. A small, named state is easier to verify than a complete algorithm. Establish it before adding the branch or loop that changes it.

2. Step 2: Pass the Short Repeat case

   Complete the readable core algorithm for one representative Interview case. Track chosen substrings in a set and maximize complete-path depth with pruning.

3. Step 3: Harden the Repeated Pattern boundary

   Repair the reviewed boundary and pass the complete submission contract. The search tries every sequence of cut positions. It rejects exactly paths repeating a chosen substring, so every complete explored path is valid and the maximum over them is optimal.

• Distinct characters are not the objective; pieces can contain multiple characters and must be distinct as whole strings.
• recursion and backtracking
• hashing and sets

• LeetCode 1593 — Split a String Into the Max Number of Unique Substrings
• Hello Interview — Backtracking Overview

• Complete One Backtracking Frame(opens in a new tab)

  Complete One Backtracking Frame isolates before expanding each choice, path equals the original caller-owned prefix; every emitted candidate contains exactly one additional element. That focused state discipline is required when implementing max unique split as a complete Interview Problem.

Backtrack over every next substring, add unseen choices to a set, and maximize the count at complete splits.

Why it works: The search tries every sequence of cut positions. It rejects exactly paths repeating a chosen substring, so every complete explored path is valid and the maximum over them is optimal.

class Solution:
    def maxUniqueSplit(self, text):
        """
        Checkpoint 1: initialize the state owned by this Interview contract.
        Checkpoint 2: assemble the primary transition without hiding the boundary.
        """
        used = set()
        best = 0
        def backtrack(start):
            nonlocal best
            if start == len(text):
                best = max(best, len(used))
                return
            if len(used) + len(text) - start <= best:
                return
            for end in range(start + 1, len(text) + 1):
                piece = text[start:end]
                if piece in used:
                    continue
                used.add(piece)
                backtrack(end)
                used.remove(piece)
        backtrack(0)
        return best