Split a String Into the Max Number of Unique Substrings

Leetcode Problem:

• Split a String Into the Max Number of Unique Substrings

Summary

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

Approach

• The approach used in this solution is a recursive depth-first search (DFS) approach
• The solution uses two data structures, a vector and a hash map, to store unique substrings and their corresponding hash values
• The DFS function recursively splits the string into substrings, checks if the substring is unique, and updates the maximum number of unique substrings found.

Complexity

• O(n * 2^n), where n is the length of the string, due to the recursive nature of the DFS function and the use of a hash map to store unique substrings.

Explanation

• The solution starts by initializing a vector and a hash map to store unique substrings and their corresponding hash values
• The DFS function is then called to recursively split the string into substrings
• For each substring, the solution checks if it is unique by checking if it exists in the hash map
• If it is unique, the solution updates the maximum number of unique substrings found
• The solution then recursively calls itself with the remaining part of the string and the updated maximum number of unique substrings
• Finally, the solution returns the maximum number of unique substrings found.

Solution Code:

#define BUCKET_SIZE 1024
struct _vector{
    string *arr;
    int size;
    int capacity;
    _vector(){
        capacity = 2;
        arr = new string[capacity];
        size = 0;
    }
    void push(string a){
        if (size == capacity){
            capacity *= 2;
            string* tmp = new string[capacity];
            for(int i = 0 ; i < size; i++){
                tmp[i] = arr[i];
            }
            delete[] arr;
            arr = tmp;
        }
        arr[size++] = a;
    }
    string operator[](int index){
        return arr[index];
    }
    void del(string s){
        int i;
        for(i = 0 ; i < size; i++){
            if(s.compare(arr[i]) == 0){
                arr[i] = arr[--size];
                break;
            }
        }
    }
};


struct _hashMap{
    _vector v[BUCKET_SIZE];
    int getHash(string& s){
        unsigned int hash = 31;
        for(int i = 0 ; i < s.size(); i++){
            hash *= s[i]-'a';
            hash %= BUCKET_SIZE;
        }
        return hash;
    }
    bool getString(string s){
        int bucket = getHash(s);
        int size = v[bucket].size;
        for(int i = 0 ; i < size; i++){
            if (v[bucket][i].compare(s) == 0){
                return true;
            }
        }
        return false;
    }
    void push(string s){
        int bucket = getHash(s);
        v[bucket].push(s);
    }
    void pop(string s){
        int bucket = getHash(s);
        v[bucket].del(s);
    }
};

class Solution {
public:
    _vector v;
    _hashMap hm;
    int ans = 0;
    void go(string s, int depth){
        ans = max(ans, depth);
        for(int i = 1 ; i <=s.size(); i++){
            string ss = s.substr(0, i);
            if(hm.getString(ss)){
                continue;
            }
            hm.push(ss);
            go(s.substr(i), depth + 1);
            hm.pop(ss);
        }
    }

    int maxUniqueSplit(string s) {
        go(s, 0);
        
        return ans;
    }
};