Count ways to increase LCS length of two strings by one - GeeksforGeeks

Count ways to increase LCS length of two strings by one - GeeksforGeeks
Given two strings of lower alphabet characters, we need to find the number of ways to insert a character in the first string such that length of LCS of both strings increases by one.

The idea is try all 26 possible characters at each position of first string, if length of str1 is m then a new character can be inserted in (m + 1) positions, now suppose at any time character c is inserted at ith position in str1 then we will match it with all positions having character c in str2. Suppose one such position is j, then for total LCS length to be one more than previous, below condition should satisfy,

LCS(str1[1, m], str2[1, n]) = LCS(str1[1, i],  str2[1, j-1]) + 
                              LCS(str1[i+1, m], str2[j+1, n])  

Above equation states that sum of LCS of the suffix and prefix substrings at inserted character must be same as total LCS of strings, so that when the same character is inserted in first string it will increase the length of LCS by one.

In below code two 2D arrays, lcsl and lcsr are used for storing LCS of prefix and suffix of strings respectively. Method for filling these 2D arrays can be found here.

Time Complexity : O(mn)
Auxiliary Space : O(mn)

int waysToIncreaseLCSBy1(string str1, string str2)

{

    int m = str1.length(), n = str2.length();

 

    // Fill positions of each character in vector

    vector<int> position[M];

    for (int i = 1; i <= n; i++)

        position[toInt(str2[i-1])].push_back(i);

 

    int lcsl[m + 2][n + 2];

    int lcsr[m + 2][n + 2];

 

    // Initializing 2D array by 0 values

    for (int i = 0; i <= m+1; i++)

        for (int j = 0; j <= n + 1; j++)

            lcsl[i][j] = lcsr[i][j] = 0;

 

    // Filling LCS array for prefix substrings

    for (int i = 1; i <= m; i++)

    {

        for (int j = 1; j <= n; j++)

        {

            if (str1[i-1] == str2[j-1])

                lcsl[i][j] = 1 + lcsl[i-1][j-1];

            else

                lcsl[i][j] = max(lcsl[i-1][j],

                                lcsl[i][j-1]);

        }

    }

 

    // Filling LCS array for suffix substrings

    for (int i = m; i >= 1; i--)

    {

        for (int j = n; j >= 1; j--)

        {

            if (str1[i-1] == str2[j-1])

                lcsr[i][j] = 1 + lcsr[i+1][j+1];

            else

                lcsr[i][j] = max(lcsr[i+1][j],

                                 lcsr[i][j+1]);

        }

    }

 

    // Looping for all possible insertion positions

    // in first string

    int ways = 0;

    for (int i=0; i<=m; i++)

    {

        // Trying all possible lower case characters

        for (char c='a'; c<='z'; c++)

        {

            // Now for each character, loop over same

            // character positions in second string

            for (int j=0; j<position[toInt(c)].size(); j++)

            {

                int p = position[toInt(c)][j];

 

                // If both, left and right substrings make

                // total LCS then increase result by 1

                if (lcsl[i][p-1] + lcsr[i+1][p+1] == lcsl[m][n])

                    ways++;

            }

        }

    }

 

    return ways;

}

Read full article from Count ways to increase LCS length of two strings by one - GeeksforGeeks