Longest String Chain

• Time : O(n len(s) n * n)

• Space : O(n)

• compare two string with length diff is 1 will take len(s) * n * n in worst case.

• worst case is there are only two group of string [len(s), len(s) - 1] and number of two groups’s difference is at most one.
• In this case, time complexity will make O(len(s) * (n / 2) * (n / 2))
• Length of TC distribution is wide, time complexity will converge to O(n * len(s) * n)

bool adj(string& origin, string& target) {
    int i = 0, j = 0, diff = 0;
    while(i < origin.size() and j < target.size() and diff < 2) {
        if(origin[i] == target[j]) {
            i++; j++;
        } else {
            i++; diff++;
        }
    }
    return diff <= 1;
}

int helper(vector<string>& A, int p, vector<int>& dp, vector<int>& path, unordered_map<int, vector<int>>& mp) {
    if(dp[p] != -1) return dp[p];
    dp[p] = 0;
    for(auto& nxt : mp[A[p].length() - 1]) {
        if(adj(A[p], A[nxt])) {
            helper(A, nxt, dp, path, mp);
            if(dp[nxt] + 1 > dp[p]) {
                dp[p] = dp[nxt] + 1;
                path[p] = nxt;
            }
        }
    }
    return dp[p];
}

vector<string> longestStringChain(vector<string> A) {
    int n = A.size(), ma = 0, p = -1;
    unordered_map<int, vector<int>> mp;
    vector<int> dp(n, -1);
    vector<int> path(n, -1);

    for(int i = 0; i < n; i++)
        mp[A[i].length()].push_back(i);

    for(int i = 0; i < n; i++) {
        if(dp[i] == -1)
            helper(A, i, dp, path, mp);
        if(ma < dp[i]) {
            ma = dp[i];
            p = i;
        }
    }

    vector<string> res;
    while(p != -1) {
        res.push_back(A[p]);
        p = path[p];
    }

    return res;
}

• Time : O(n len(s) len(s))

• Space : O(n)

• making smaller string will take len(s) * len(s)

vector<string> smaller(string& s) {
    vector<string> res;
    for(int i = 0; i < s.length(); i++) {
        res.push_back(s.substr(0,i) + s.substr(i+1));
    }
    return res;
}

int helper(vector<string>& A, int p, vector<int>& dp, vector<int>& path, unordered_map<string, int>& mp) {
    if(dp[p] != -1) return dp[p];
    dp[p] = 0;
    for(auto& nxt : smaller(A[p])) {
        if(mp.count(nxt)) {
            helper(A, mp[nxt], dp, path, mp);
            if(dp[mp[nxt]] + 1 > dp[p]) {
                dp[p] = dp[mp[nxt]] + 1;
                path[p] = mp[nxt];
            }
        }
    }
    return dp[p];
}

vector<string> longestStringChain(vector<string> A) {
    int n = A.size(), ma = 0, p = -1;
    unordered_map<string, int> mp;
    vector<int> dp(n, -1);
    vector<int> path(n, -1);

    for(int i = 0; i < n; i++)
        mp[A[i]] = i;

    for(int i = 0; i < n; i++) {
        if(dp[i] == -1)
            helper(A, i, dp, path, mp);
        if(ma < dp[i]) {
            ma = dp[i];
            p = i;
        }
    }

    vector<string> res;
    while(p != -1) {
        res.push_back(A[p]);
        p = path[p];
    }

    return res;
}