PROBLEM LINK:Author: Misha Chorniy DIFFICULTY:Medium PREREQUISITES:DP, Longest Common Subsequence Algorithm PROBLEM:Given two strings of equal length, we have to report the $k^{th}$ lexicographical longest common subsequence. In other words, let the strings be $S_1$ and $S_2$. Let L be the length of the longest common subsequence. Let P be the set of all the subsequences which are common to $S_1$ and $S_2$ and are of the length L. We have to report the $k^{th}$ element in this set P when it is sorted lexicographically. EXPLANATION:Note: For the sake of simplicity, throughtout the editorial, we assume that $S[1]$ is the first character of the string, i.e., all strings are 1indexed. The Longest Common Subsequence (LCS) is a very common problem. The traditional approach uses DP. Let $L[i][j]$ be the length of the LCS when considering the last $i$ characters of $S_1$ and $j$ characters of $S_2$. We can formulate the recurrence for $L[i][j]$:
Now, let us find a way to count distinct longest common subsequences. Let $D[i][j]$ be the number of LCS of length $L[i][j]$ when considering the last $i$ characters of $S_1$ and $j$ characters of $S_2$, i.e., it gives the number of distinct LCS for substrings $S_1[i..n]$ and $S_2[j..n]$. Now, we formulate the recurrence for this:
Now, before we move on to formalizing the algorithm, we have another observation to make: Now, we have all the essential elements for the formal algorithm. $L[1][1]$ gives the length of the LCS for the input strings. Set $L[0][0] = L[1][1]+1$. $D[1][1]$ gives the number of distinct LCS of length $L[1][1]$. Set $D[0][0] = 0$. Let us keep two more arrays, pointer_S1[n][26] and pointer_S2[n][26]. Both of them serve the same purpose, but one is for string $S_1$ and the other for string $S_2$. The purpose is that pointer_S1[i][j] stores the index $p$ such that $p > i$ and $S_1[p]$ = $j^{th}$ lower case letter. In other words, pointer_S1[i][0] stores the index $p$ where $p$ is the smallest index greater than $i$ such that $S_1[p] =$ 'a'. If there is no occurrence of the particular letter after index $i$, then $1$ is stored. Let us see how we can get the required string from the above structures. If $k > D[1][1]$, we can simply output $1$ since there is no answer. Otherwise, we start at $L[0][0]$. We want to move to such an $i$, $j$ such that the following conditions are met:
If all these conditions are met, we will append the letter $S_1[i]$ ($= S_2[j]$) to our answer. With the help of the pointer_S1 and pointer_S2 arrays, we can iterate over all possible $i$, $j$ to find the letter we require. We repeat this till we reach an $i$, $j$ such that $L[i][j] = 1$. A pseudocode of this procedure is provided below:
Other implementation details can be seen from the editorialist's solution. COMPLEXITY:$\mathcal{O}(n^2)$ SAMPLE SOLUTIONS:
This question is marked "community wiki".
asked 18 Dec '15, 12:59

http://pastie.org/10647199  my code http://pastie.org/10647207  tester http://pastie.org/10647204  editorialist answered 22 Dec '15, 18:49

None of the given sample solutions are visible. Every link shows "Access Denied"! answered 22 Dec '15, 09:18

Here is my code.. https://www.codechef.com/viewsolution/8997375 I got Wa. please help me where is my wrong. give some critical test case. thanks in advance answered 22 Dec '15, 08:52

Since, the author, tester and editorialist's codes are not available, can someone give link to someone's code, who has followed the approach stated above? Thanks in advance! answered 22 Dec '15, 10:44

If S1[i]=S2[j] then L[i][j]=L[i+1][j+1]+1. Correct it
the editorial is marked "community wiki". this means that if you spot errors, you can correct them directly. please feel free to do so :)