PROBLEM LINK:
Author: Misha Chorniy
Tester: Jingbo Shang
Editorialist: Pushkar Mishra
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 1-indexed.
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]:
- If S_1[i] = S_2[j] then L[i][j] = L[i+1][j+1]+1.
- If S_1[i] \neq S_2[j] then L[i][j] = max(L[i+1][j], L[i][j+1]).
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:
- If S_1[i] = S_2[j] then D[i][j] = D[i+1][j+1].
- If S_1[i] \neq S_2[j] and L[i][j] = L[i+1][j], then D[i][j] = D[i+1][j].
- If S_1[i] \neq S_2[j] and L[i][j] = L[i][j+1], then D[i][j] = D[i][j+1].
- If S_1[i] \neq S_2[j] and L[i+1][j] = L[i][j+1], then D[i][j] = D[i][j+1]+D[i+1][j] - D[i+1][j+1].
Now, before we move on to formalizing the algorithm, we have another observation to make:
Let their be two strings S_1 = abcddpq and S_2 = axbedff. Consider the LCS in the two strings up till the index 2 (starting index = 1), i.e., ab. Now, let us consider how to extend the LCS when taking letters after index 2. We see that we can append a d to make the LCS abd. But, S_1 has 2 d. Which one should be used to extend? In this example, it doesn’t matter. But what if S_2 was axbedfd. We see that it is always favorable to match the earliest appearences of a character in the two strings whenever that is possible. This way, the following appearences of that character can be used to extend the LCS.
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:
- L[i][j] = L[0][0] - 1
- S_1[i] = S_2[j]
- The number of strings with letters smaller than S_1[i] in this position is less than the k
- The number of strings with letters smaller than AND EQUAL TO S_1[i] in this position is \geq k.
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:
function get_string()
{
String ans = "";
i, j = 0;
L[0][0] = L[1][1] + 1;
while(L[i][j] > 1)
{
count, new_count = 0;
for( character c = 'a' to 'z')
{
//Getting the next_i and next_j based on pointer arrays.
next_i = pointer_S1[i][c];
next_j = pointer_S2[j][c];
if(next_i or next_j == -1)
skip to next letter;
if(L[next_i][next_j] != L[i][j] - 1)
letter c doesn't lie on the desired LCS. Thus skip to next letter.
//Producing new_count based on count and the number of distinct LCS between
//substrings S1[next_i..n] and S2[next_j..n].
new_count = count + D[next_i][next_j];
//checking whether last condition is fulfilled or not
if(count < k and k <= new_count)
{
//we have found the letter to extend the desired LCS.
k = k-count;
i = next_i;
j = next_j;
ans = ans + c;
//breaking the loop since letter has been found
break;
}
count = new_count;
}
}
return ans;
}
Other implementation details can be seen from the editorialist’s solution.
COMPLEXITY:
\mathcal{O}(n^2)
