Split a String Into the Max Number of Unique Substrings

class Solution {
public:
    int maxUniqueSplit(string s) {
        int best = 1;
        unordered_set<string> used;
        function<void(int,int)> dfs = [&](int i, int cnt) {
            if (cnt + (int)(s.size() - i) <= best) return; // prune
            if (i == (int)s.size()) { best = max(best, cnt); return; }
            for (int j = i + 1; j <= (int)s.size(); ++j) {
                string piece = s.substr(i, j - i);
                if (used.insert(piece).second) {
                    dfs(j, cnt + 1);
                    used.erase(piece);
                }
            }
        };
        dfs(0, 0);
        return best;
    }
};

func maxUniqueSplit(s string) int {
    best := 1
    used := map[string]bool{}
    var dfs func(i, cnt int)
    dfs = func(i, cnt int) {
        if cnt+(len(s)-i) <= best {
            return // prune
        }
        if i == len(s) {
            if cnt > best {
                best = cnt
            }
            return
        }
        for j := i + 1; j <= len(s); j++ {
            piece := s[i:j]
            if !used[piece] {
                used[piece] = true
                dfs(j, cnt+1)
                delete(used, piece)
            }
        }
    }
    dfs(0, 0)
    return best
}

class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        self.best = 1
        used: set[str] = set()
        n = len(s)

        def dfs(i: int, cnt: int) -> None:
            if cnt + (n - i) <= self.best:
                return  # prune
            if i == n:
                if cnt > self.best:
                    self.best = cnt
                return
            for j in range(i + 1, n + 1):
                piece = s[i:j]
                if piece not in used:
                    used.add(piece)
                    dfs(j, cnt + 1)
                    used.remove(piece)

        dfs(0, 0)
        return self.best

function maxUniqueSplit(s) {
    let best = 1;
    const used = new Set();
    const n = s.length;
    const dfs = (i, cnt) => {
        if (cnt + (n - i) <= best) return; // prune
        if (i === n) {
            if (cnt > best) best = cnt;
            return;
        }
        for (let j = i + 1; j <= n; j++) {
            const piece = s.substring(i, j);
            if (!used.has(piece)) {
                used.add(piece);
                dfs(j, cnt + 1);
                used.delete(piece);
            }
        }
    };
    dfs(0, 0);
    return best;
}

class Solution {
    private int best;
    private String s;
    private int n;
    private Set<String> used = new HashSet<>();

    private void dfs(int i, int cnt) {
        if (cnt + (n - i) <= best) return; // prune
        if (i == n) {
            if (cnt > best) best = cnt;
            return;
        }
        for (int j = i + 1; j <= n; j++) {
            String piece = s.substring(i, j);
            if (used.add(piece)) {
                dfs(j, cnt + 1);
                used.remove(piece);
            }
        }
    }

    public int maxUniqueSplit(String s) {
        this.s = s;
        this.n = s.length();
        this.best = 1;
        dfs(0, 0);
        return best;
    }
}

function maxUniqueSplit(s: string): number {
    let best = 1;
    const used = new Set<string>();
    const n = s.length;
    const dfs = (i: number, cnt: number): void => {
        if (cnt + (n - i) <= best) return; // prune
        if (i === n) {
            if (cnt > best) best = cnt;
            return;
        }
        for (let j = i + 1; j <= n; j++) {
            const piece = s.substring(i, j);
            if (!used.has(piece)) {
                used.add(piece);
                dfs(j, cnt + 1);
                used.delete(piece);
            }
        }
    };
    dfs(0, 0);
    return best;
}