### 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.

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] = summation of dp[i-1][j-1][k][0...2];

dp[i][j][k] = (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] = (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.  Comments (10)
 » Auto comment: topic has been updated by Varun_Shah (previous revision, new revision, compare).
 » Auto comment: topic has been updated by Varun_Shah (previous revision, new revision, compare).
 » 3 years ago, # | ← Rev. 3 →   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 and dpdp is old data, and dp 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 and b are empty.In the kth iteration,dp[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 = 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[y][j] for all j like so: for (int x = 0; x < y; x++) { dp[y][j] += dp[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[i][j] for all 1 <= i <= |a|, 1 <= j <= |b|
•  » » So you mean to say that for ith character match of c, first we need to fill dp which stores answer of matching only i characters then update dp based on dp...do this for c.length() iterations...Correct me if I am wrong.
•  » » » No. I meant that if we are processing the ith character of string c, then dp 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 and then copy it back to dp. (We use dp as a temporary array, as we need values in dp till the end of the current iteration).
•  » » 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)?
•  » » » 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 to dp — O(|a|*|b|).Overall complexity — O(|c|*|a|*|b|).Here's my submission for ref. — https://paste.ubuntu.com/p/k66BGsM7rQ/
•  » » » » Okay got it...except for how does it take care for atleast 1 character from both string?
•  » » » » » "After all iterations, the ans will be sum of dp[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)
 » 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?