thảo luận Leetcode mỗi ngày

class Solution {
    int res =0;
    public int maxUniqueSplit(String s) {
        int n = s.length();
        Set<String> set = new HashSet<>();
        backtrack(s,set,0,0);
        return res;
    }
    public void backtrack(String s, Set<String> set  ,int start, int cur){
        if(start>=s.length()){
            res = Math.max(res, cur);
        }
        for(int i =start;i<s.length();i++ ){
            for(int j = i+1;j<=s.length();j++){
                String substring = s.substring(i,j);
                if(!set.contains(substring)){
                    set.add(substring);
                    backtrack(s,set,j,cur+1);
                    set.remove(substring);
                }
            }
        }
    }

class Solution {
    int res = 0;
    public int maxUniqueSplit(String s) {
        int n = s.length();
        Set<String> set = new HashSet<>();
        backtrack(s, set, 0, 0);
        return res;
    }

    public void backtrack(String s, Set<String> set, int start, int cur) {
        if (start >= s.length()) {
            res = Math.max(res, cur);
        }
        for (int i = start+1; i <= s.length(); i++) {
            String substring = s.substring(start, i);
            if (!set.contains(substring)) {
                set.add(substring);
                backtrack(s, set, i, cur + 1);
                set.remove(substring);
            }
        }
    }
}

class Solution {
    public int maxUniqueSplit(String s) {
        return backtrack(0, s, new HashSet<>());
    }

    private int backtrack(int index, String string, Set<String> set) {
        if (index == string.length()) {
            return 0;  
        }
        int max = 0;
        for (int i = index + 1; i <= string.length(); i++) {
            String sub = string.substring(index, i);
            if (set.contains(sub)) continue;
            set.add(sub);
            max = Math.max(max, 1 + backtrack(i, string, set));
            set.remove(sub);
        }
        return max;
    }
}

class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        seen = set()
        def backtrack(start, seen):
            if start == len(s):
                return 0
            
            max_splits = 0
            for end in range(start + 1, len(s) + 1):
                substring = s[start:end]
                # If this substring hasn't been used before
                if substring not in seen:
                    # Add substring to the set and backtrack
                    seen.add(substring)
                    # Recursively find the number of splits from this point onward
                    max_splits = max(max_splits, 1 + backtrack(end, seen))
                    # Backtrack: remove the substring from the set
                    seen.remove(substring)
            return max_splits
        return backtrack(0, seen)

class Solution {
    char[] arr;
    int max;
    Set<String> set = new HashSet<>();

    public int maxUniqueSplit(String s) {
        arr = s.toCharArray();
        backtrack(0, "");
        return max;
    }

    void backtrack(int i, String cur) {
        if (i == arr.length)
            return;

        cur += arr[i];

        if (!set.contains(cur)) {
            set.add(cur);

            max = Math.max(max, set.size());

            backtrack(i + 1, "");
            set.remove(cur);
        }

        backtrack(i + 1, cur);
    }
}

class Solution {
    func maxUniqueSplit(_ s: String) -> Int {

        var maxCount = 0
        var unique:Set<[Character]> = []

        let s = [Character](s)

        func backtrack(_ start: Int) {
            guard start < s.count else {
                maxCount = max(maxCount, unique.count)
                return
            }
            var nextString:[Character] = []
            for index in start..<s.count {
                nextString.append(s[index])
                if !unique.contains(nextString) {
                    unique.insert(nextString)
                    backtrack(index + 1)
                    unique.remove(nextString)
                }
            }
        }

        backtrack(0)
        return maxCount
    }
}

class Solution {   
#if MY_DEBUG
    set<string> _st;
#endif
public:
    int maxUniqueSplit(string s) {
        set<string> st;
        int maxCount = 0;
        backtrack(s, st, maxCount, 0, s.length(), 0);
#if MY_DEBUG
        cout << "Splitted string:" << endl;
        for (auto it = _st.begin(); it != _st.end(); ++it) {
            cout << *it << " ";
        }
#endif
        return maxCount;
    }

    void backtrack(string& s, set<string>& st, int& maxCount, size_t from, size_t len, int count) {
        if (from == len) {       
            #if MY_DEBUG
            if (maxCount < count)   
                _st = st;
            #endif // MY_DEBUG
            
            maxCount = max(maxCount, count);
            return;
        }
        if (maxCount >= count + len - from)
            return;
        string str;
        str.reserve(len - from);
        for (size_t i = from; i < len; ++i) {
            str += s[i];
            if (st.find(str) == st.end()) {
                st.insert(str);
                backtrack(s, st, maxCount, i + 1, len, count + 1);
                st.erase(str);
            }
        }
    }
};

class Solution {
    Set<String> set = new HashSet();
    Stack<String> stack = new Stack();
    int maxLen;
    public int maxUniqueSplit(String s) {
        maxLen = 0;
        backtrack(s,0,1);
        return maxLen;
    }

    public void backtrack(String s, int start, int size){
        int n = s.length();
        if(start>n) {
            if(!set.isEmpty())
                set.remove(stack.pop());
            return;
        }
        while(start+size <= n){
            String sub = s.substring(start,start+size);
            if(!set.contains(sub)){
                stack.add(sub);
                set.add(sub);
                backtrack(s,start+size,1);
            }       
            size+=1;
        }
        if(start == n)
            maxLen = Math.max(maxLen,set.size());
        if(!set.isEmpty())
            set.remove(stack.pop()); 
        return;
    }
}

use std::collections::HashSet;

const Q: u32 = 1_000_000_009;

impl Solution {
    pub fn max_unique_split(s: String) -> i32 {
        fn helper(bytes: &[u8], seen: &mut HashSet<u32>, count: i32) -> i32 {
            if bytes.is_empty() {
                return count;
            }

            let (mut hash, mut max_count) = (0, 0);

            for (i, bc) in bytes.iter().copied().enumerate() {
                hash = ((hash * 31) + bc as u32) % Q;

                if seen.contains(&hash) {
                    continue;
                }

                seen.insert(hash);
                max_count = max_count.max(helper(&bytes[(i + 1)..], seen, count + 1));
                seen.remove(&hash);
            }

            max_count
        }

        helper(s.as_bytes(), &mut HashSet::new(), 0)
    }
}

public class Solution
{
    public int MaxUniqueSplit(string s)
    {
        int length = s.Length;
        HashSet<string> set = new();

        int result = int.MinValue;
        Backtrack(s, set, ref result);

        return result;
    }

    private void Backtrack(string s, HashSet<string> set, ref int result)
    {
        if (s == string.Empty)
        {
            result = Math.Max(result, set.Count);
            return;
        }
        for (int i = 0; i < s.Length; i++)
        {
            string subString = s.Substring(0, i + 1);
            if (set.Contains(subString))
            {
                continue;
            }
            set.Add(subString);
            string remain = s.Substring(i + 1, s.Length - i - 1);
            Backtrack(remain, set, ref result);
            set.Remove(subString);
        }
    }
}

class Solution {
    int res = 1;
    public int maxUniqueSplit(String s) {
        Set<String> set = new HashSet<>();
        backtrack(set, s, 0);
        return res;
    }

    private void backtrack(Set<String> set, String s, int curr) {
        if (curr == s.length()) {
            res = Math.max(res, set.size());
        }

        for (int i = curr + 1; i <= s.length(); i++) {
            String str = s.substring(curr, i);
            if (set.contains(str)) {
                continue;
            }
            set.add(str);
            backtrack(set, s, i);
            set.remove(str);
        }
    }
}