Given a string&nbsp;s,&nbsp;return the maximum&nbsp;number of unique substrings that the given string can be split into.

You can split string&nbsp;s into any list of&nbsp;non-empty substrings, where the concatenation of the substrings forms the original string.&nbsp;However, you must split the substrings such that all of them are unique.

A substring is a contiguous sequence of characters within a string.

&nbsp;
Example 1:

Input: s = "ababccc"
Output: 5
Explanation: One way to split maximally is ['a', 'b', 'ab', 'c', 'cc']. Splitting like ['a', 'b', 'a', 'b', 'c', 'cc'] is not valid as you have 'a' and 'b' multiple times.


Example 2:

Input: s = "aba"
Output: 2
Explanation: One way to split maximally is ['a', 'ba'].


Example 3:

Input: s = "aa"
Output: 1
Explanation: It is impossible to split the string any further.


&nbsp;
Constraints:


	
	1 &lt;= s.length&nbsp;&lt;= 16
	
	
	s contains&nbsp;only lower case English letters.
	


class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        ans, n = 0, len(s)
        def dfs(i, cnt, visited):
            nonlocal ans, n
            if i == n: ans = max(ans, cnt); return  # stop condition
            for j in range(i+1, n+1):    
                if s[i:j] in visited: continue      # avoid re-visit/duplicates
                visited.add(s[i:j])                 # update visited set
                dfs(j, cnt+1, visited)              # backtracking
                visited.remove(s[i:j])              # recover visited set for next possibility
        dfs(0, 0, set())                            # function call
        return ans
class Solution {
    int max = 0;
    public int maxUniqueSplit(String s) {
        int n = s.length();
        backtrack(s, 0, new HashSet<String>());
        return max;
    }
    public void backtrack(String s, int start, Set<String> h) {
        if(start == s.length()) {
            max = Math.max(max, h.size());
        }
        String res = "";
        
        for(int i = start;i < s.length();i++) {
            res += s.charAt(i);
            if(h.contains(res)) continue;
            h.add(res);
            backtrack(s, i+1, h);
            h.remove(res);
        }
    }
}
class Solution {
public:
    unordered_set<string>st;
    int ans=0;
    void dfs(string &s, int idx)
    {
        if(st.size()>ans) ans=st.size();
        if(idx>=s.length()) return;
        string str="";
        for(int i=idx ; i<s.length() ; i++)
        {
            str += s[i];
            if(st.find(str)==st.end())
            {
                st.insert(str);
                dfs(s,i+1);
                st.erase(str);
            }
        }
    }
    
    int maxUniqueSplit(string s) {
        dfs(s,0);
        return ans;
    }
};
var maxUniqueSplit = function(s) {
    let wordSet = new Set(), res = 1;
    
    function checkUniqueSubstring(i) {
        if (i === s.length) {
            res = Math.max(wordSet.size, res);
            return;
        }
        
        for (let j = i+1; j <= s.length; j++) {
            let str = s.substring(i,j);
            if (!wordSet.has(str)) {
                wordSet.add(str);
                checkUniqueSubstring(j);
                wordSet.delete(str);
            }
        }
    }
    
    checkUniqueSubstring(0);
    
    return res;
};
Split a String Into the Max Number of Unique Substrings