PROBLEM LINK:
Author: Alisha M Baji
Tester: Alex Mathew
Editorialist: Alex Mathew
DIFFICULTY:
MEDIUM
PREREQUISITES:
DYNAMIC-PROGRAMMING
PROBLEM:
Rahul and Kiran were talking with each other. Suddenly Anju came towards them and
reminded them of a previous challenge she had given them and they failed. So They too
decide to give her a unique challenge to teach her a lesson. They tell her that they will each recite a word and Anju has to find out the one unique word that is made out of common alphabets of the word spoken by them, taken in order. Anju should tell the word/string that appears in the same relative order, but not necessarilycontiguous.
For example, “abc”, “abg”, “bdf”, “aeg”, ‘”acefg”, … etc are the common
subsequence of “abcdefg”.
EXPLANATION:
To solve this we use dynamic programming. We use a matrix to optimize the problem and result is obtained after filling it.
First we define a matrix with T[n+1][m+1], where n and m are the length of two strings. Let the input sequences be X[0…m-1] and Y[0…n-1] of lengths m and n respectively. We initialize the first row and column with zeros.
Traverse the matrix for every cell T[i][j]. If characters X[i-1] equals Y[j-1] then then include this character as part of LCS. Otherwise compare values of L[i-1][j] and L[i][j-1] and go in direction of greater value.
BASIC FUNCTION
/*Returns length of LCS for X[0…m-1], Y[0…n-1] */
int lcs( char *X, char *Y, int m, int n )
{
int L[m+1][n+1];
int index;
int i,j;
char *lcs;
int len;
/* Following steps build L[m+1][n+1] in bottom up fashion. Note
that L[i][j] contains length of LCS of X[0..i-1] and Y[0..j-1] */
for (i=0; i<=m; i++)
{
for (j=0; j<=n; j++)
{
if (i == 0 || j == 0)
L[i][j] = 0;
else if (X[i-1] == Y[j-1])
L[i][j] = L[i-1][j-1] + 1;
else
L[i][j] = max(L[i-1][j], L[i][j-1]);
}
}
// Following code is used to print LCS
index = L[m][n];
len = index;
// Create a character array to store the lcs string
lcs = (char*)(malloc(sizeof(index+1)));
lcs[index] = '\0'; // Set the terminating character
// Start from the right-most-bottom-most corner and
// one by one store characters in lcs[]
i = m, j = n;
while (i > 0 && j > 0)
{
// If current character in X[] and Y are same, then
// current character is part of LCS
if (X[i-1] == Y[j-1]){
lcs[index-1] = X[i-1]; // Put current character in result
i--; j--; index--; // reduce values of i, j and index
}
// If not same, then find the larger of two and
// go in the direction of larger value
else if (L[i-1][j] > L[i][j-1])
i--;
else
j--;
}
// Print the lcs
//cout << "LCS of " << X << " and " << Y << " is " << lcs;
printf("%s ",lcs);
return len;
}
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.