DSA Notes

Longest Common Subsequence (LCS) in two strings

• A subsequence of a string is a list of characters of the string where some characters are deleted ( or not deleted at all) and they should be in the same order in the subsequence as in the original string.
• For a string of length n, the number of subsequences will be 2n.

Memoization

class Solution {
public:
    int longestCommonSubsequence(string s1, string s2) {
        int n = s1.size();
        int m = s2.size();
        vector<vector<int>> dp(n, vector<int>(m, -1));
        return f(n-1, m-1, s1, s2, dp);
    }
    // f(ind1, ind2) → Longest common subsequence of S1[0...ind1] and S2[0...ind2]
    int f(int i1, int i2, string s1, string s2, vector<vector<int>>& dp){
        if (i1 < 0 || i2 < 0) return 0;
        if (dp[i1][i2] != -1) return dp[i1][i2];
        if (s1[i1] == s2[i2]) {
            return dp[i1][i2] = 1 + f(i1-1, i2-1, s1, s2, dp);
        } else {
            return dp[i1][i2] = max(f(i1-1, i2, s1, s2, dp), f(i1, i2-1, s1, s2, dp));
        }    
    }
};

Tabulation

class Solution{
public:
    int longestCommonSubsequence(string s1, string s2){
        int n = s1.size();
        int m = s2.size();
        
        vector<vector<int>> dp(n + 1, vector<int>(m + 1, -1)); 

        // base cases
        for (int i = 0; i <= n; i++) {
            dp[i][0] = 0;
        }
        for (int i = 0; i <= m; i++) {
            dp[0][i] = 0;
        }
        // Fill in the DP table
        for (int i1 = 1; i1 <= n; i1++) {
            for (int i2 = 1; i2 <= m; i2++) {
                
                // Characters match, increment LCS length
                if (s1[i1 - 1] == s2[i2 - 1]) dp[i1][i2] = 1 + dp[i1 - 1][i2 - 1]; 

                // Characters don't match, consider the maximum from left or above 
                else dp[i1][i2] = max(dp[i1 - 1][i2], dp[i1][i2 - 1]); 
            }
        }
        return dp[n][m]; 
    }
};

Print Longest Common Subsequence (LCS) of two strings

• similar after last question when we create a 2D DP table to store lengths of longest common subsequence, then we backtrack and construct the LCS string from dp[n][m] to find the actual LCS string.

class Solution {
public:
    string longestCommonSubsequence(string &s1, string &s2) {
        int n = s1.size();
        int m = s2.size();

        vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));

        // Fill dp table using bottom-up
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (s1[i - 1] == s2[j - 1]) {
                    dp[i][j] = 1 + dp[i - 1][j - 1];
                } else {
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }

        // Reconstruct LCS string from dp table
        int i = n, j = m;
        string lcs = "";

        // Traverse dp table from bottom-right to top-left
        while (i > 0 && j > 0) {
            if (s1[i - 1] == s2[j - 1]) {
                // Characters match, add to result and move diagonally
                lcs += s1[i - 1];
                i--;
                j--;
            } else if (dp[i - 1][j] > dp[i][j - 1]) {
                i--;   // Move up if top cell has greater value
            } else {
                j--;   // Move left otherwise
            }
        }

        reverse(lcs.begin(), lcs.end()); // Reverse string since it was built backwards
        return lcs;
    }
};

Longest Common Substring

class Solution {
public:
    int longestCommonSubstring(string s1, string s2) {
        int n = s1.size();
        int m = s2.size();  
        vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
        int maxLen = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (s1[i - 1] == s2[j - 1]) { // Characters match, increment substring length
                    dp[i][j] = 1 + dp[i - 1][j - 1];
                    maxLen = max(maxLen, dp[i][j]);
                } else {
                    dp[i][j] = 0; // Reset since substring must be contiguous
                }
            }
        }
        return maxLen;
    }
};

Longest Palindromic Subsequence

• we reverse the given string and find the LCS between the original string and the reversed string.

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        string t = s;
        reverse(t.begin(), t.end());
        int n = s.size();
        vector<vector<int>> dp(n+1, vector<int>(n+1, -1));

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

        for (int i = 1; i <= n; i++){
            for (int j = 1; j <= n; j++){
                if (s[i-1] == t[j-1]) dp[i][j] = 1 + dp[i-1][j-1];
                else dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            }
        }
        return dp[n][n];
    }
};

Minimum insertions to make string palindrome

• In order to minimize the insertions, we need to find the length of the longest palindromic component or in other words, the longest palindromic subsequence. Minimum Insertion required = n(length of string) - length of longest palindromic subsequence.

class Solution {
public:
    int lcs(string s, string t){
        int n = s.size();
        vector<vector<int>> dp(n+1, vector<int>(n+1, -1));
        for (int i = 0; i < n; i++) dp[i][0] = 0;
        for (int i = 0; i < n; i++) dp[0][i] = 0;

        for (int i = 1; i <= n; i++){
            for (int j = 1; j <= n; j++){
                if (s[i-1] == t[j-1]) dp[i][j] = 1 + dp[i-1][j-1];
                else dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            }
        }

        return dp[n][n];
    }
    int minInsertions(string s) {
        int n = s.size();
        string t = s;
        reverse(t.begin(), t.end());
        int l = lcs(s, t);
        return n - l;
    }
};

Shortest Common Supersequence

• We are given two strings ‘S1’ and ‘S2’. We need to return their shortest common supersequence. A supersequence is defined as the string which contains both the strings S1 and S2 as subsequences.

• Approach :- Shortest Common Supersequence (SCS) is basically formed by merging both strings while writing the Longest Common Subsequence (LCS) only once. If we just concatenate, we repeat many characters unnecessarily; instead, LCS gives the maximum set of characters already common in correct order, so we keep them single and only insert the “extra” non-LCS characters from both strings around them. Using the LCS DP table, we backtrack from dp[n][m]: when characters match, we take it once and move diagonally; when they don’t, we move in the direction of the larger DP value and add the skipped character, finally reversing the built string to get the SCS.

• length of the shortest Common supersequence = n + m - k,

class Solution {
public:
    string shortestCommonSupersequence(string str1, string str2) {
        int n = str1.size();
        int m = str2.size();
        vector<vector<int>> dp(n+1, vector<int>(m+1, -1));
        for (int i = 0; i < n; i++) dp[i][0] = 0;
        for (int i = 0; i < m; i++) dp[0][i] = 0;
        for (int i = 1; i <= n; i++){
            for (int j = 1; j <= m; j++){
                if (str1[i-1] == str2[j-1]) dp[i][j] = 1 + dp[i-1][j-1];
                else dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            }
        }

        int i = n;
        int j = m;
        string ans = "";
        while (i > 0 && j > 0){
            if (str1[i-1] == str2[j-1]){
                ans += str1[i-1];
                i--;
                j--;
            } else if (dp[i-1][j] > dp[i][j-1]){
                ans += str1[i-1];
                i--;
            } else {
                ans += str2[j-1];
                j--;
            }
        }
        while (i > 0){
            ans += str1[i-1];
            i--;
        }
        while (j > 0){
            ans += str2[j-1];
            j--;
        }
        reverse(ans.begin(), ans.end());
        return ans;
    }
};

Distinct Subsequences

• Given two strings s and t, return the number of distinct subsequences of s which equals t.

class Solution {
public:
    int numDistinct(string s, string t) {
        int n = s.size();
        int m = t.size();
        
        // dp[i][j] = no. of distinct subsequences of s[0…i-1] that form t[0…j-1]
        vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));

        for (int i = 0; i <= n; i++) {
            dp[i][0] = 1;
        }

        // Fill dp table from bottom to top
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                // If characters match, we have two options:
                // pick this character -> dp[i-1][j-1] ; skip this character -> dp[i-1][j]
                if (s[i-1] == t[j-1]) {
                    dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
                } else {
                    // If characters don't match, we can only skip
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
        return dp[n][m];
    }
};