### Varun_Shah's blog

By Varun_Shah, history, 3 years ago,

I found the following problem very interesting on a recent Hackerrank contest, I don't get the intuition for what the editorialist states.It would indeed be very helpful if someone helps me understand it.

Link to the problem

What I got is as follows:

(Note:dp[x...y] means dp[x] + dp[x+1] ... + dp[y])

for number of ways of reaching a solution from either string a or string b, the recurrence may go as follows

dp[i][j][k][0] = summation of dp[i-1][j-1][k][0...2];

dp[i][j][k][1] = (if a[i] equals c[k] then summation of dp[i-1][j][k-1][0...2] else 0) + dp[i-1][j][k][0...2];

dp[i][j][k][2] = (if b[j] equals c[k] then summation of dp[i][j-1][k-1][0...2] else 0) + dp[i][j-1][k][0...2];

Here, dp[i][j][k][x] means number of ways of forming c[0...k] from a[0...i] or from b[0...j] or both.

where x = 0 if we neglect last character of both a and b

x = 1 if we consider last character of a and not b

x = 2 if we consider last character of b and not a

Please correct me if I am wrong.Thanks in advance for the help.

• +5

 » 3 years ago, # |   0 Auto comment: topic has been updated by Varun_Shah (previous revision, new revision, compare).
 » 3 years ago, # |   0 Auto comment: topic has been updated by Varun_Shah (previous revision, new revision, compare).
 » 3 years ago, # | ← Rev. 3 →   +15 I didn't read the editorial, but I thought of explaining what I did (it seems to be simpler than editorial). Maybe someone will find it useful. We will use two 2D arrays dp[0] and dp[1]dp[0] is old data, and dp[1] is the data of current character, which will be updated.We start from the first character of string c, and traverse to the end. Counting is 1-indexed. a[0] and b[0] are empty.In the kth iteration,dp[0][i][j] = number of ways of having character a[i] as last character chosen in a, character b[j] as last character chosen in b and arranged to form c[1..(k-1)].Clearly, the base case is dp[0][0][0] = 1 (1 way to satisfy empty string c using nothing from a and nothing from b).In each iteration, we have 2 cases. Case 1: The current character will be taken care of by a character chosen from string a.We go through all characters in string a, and for those characters where a[y] = c[k], where k is the iteration number, we update dp[1][y][j] for all j like so: for (int x = 0; x < y; x++) { dp[1][y][j] += dp[0][x][j]; } I wrote that for loop to just to represent what I meant. A running sum must be used instead to get rid of this O(|a|) extra time. The reason for us doing this is — We have some solutions for c[1..(k-1)] with x as last char in a, j as last char in b. We are using yth character from a in this iteration, so we add all possible solutions that can be extended to this iteration.Case 2: The current character will be taken care of by a character chosen from string b.We do the same thing as Case 1 — fixing position in string a instead of b. At the end of each iteration, we need to copy new values into old.After all iterations, the ans will be sum of dp[0][i][j] for all 1 <= i <= |a|, 1 <= j <= |b|
•  » » 3 years ago, # ^ |   0 So you mean to say that for ith character match of c, first we need to fill dp[0] which stores answer of matching only i characters then update dp[1] based on dp[0]...do this for c.length() iterations...Correct me if I am wrong.
•  » » » 3 years ago, # ^ |   0 No. I meant that if we are processing the ith character of string c, then dp[0] will have the solution for the substring c[1..(i-1)]. We will use this information to find the answer for the substring c[1..i]. We store this in dp[1] and then copy it back to dp[0]. (We use dp[1] as a temporary array, as we need values in dp[0] till the end of the current iteration).
•  » » 3 years ago, # ^ |   0 To update dp1:For every k from 1 to c.size(), for all possible lengths of a & b, we find if(a[i] == c[k]) and then in the same way if(b[j] == c[k]). If condition holds true, we again iterate over entire respective string's array...Won't that exceed the TL as it becomes O(n^4)?
•  » » » 3 years ago, # ^ |   0 We do |c| iterations.In each iteration:In case 1, we will iterate over all possible positions for string b, and then for each of them, we will iterate over all possible positions for string a — O(|b|*|a|).In case 2, we will iterate over all possible positions for string a, and then for each of them, we will iterate over all possible positions for string b — O(|a|*|b|).Copying dp[1] to dp[0] — O(|a|*|b|).Overall complexity — O(|c|*|a|*|b|).Here's my submission for ref. — https://paste.ubuntu.com/p/k66BGsM7rQ/
•  » » » » 3 years ago, # ^ |   0 Okay got it...except for how does it take care for atleast 1 character from both string?
•  » » » » » 3 years ago, # ^ |   +1 "After all iterations, the ans will be sum of dp[0][i][j] for all 1 <= i <= |a|, 1 <= j <= |b|".The conditions i >= 1 and j >= 1 take care of atleast 1 character from both strings. (i/j = 0 implies no character from a/b)
 » 4 weeks ago, # |   0 Hey I know its been 3 years, but I am trying to understand the problem now but still can't understand the editorial. Why do we need the 4th state?