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][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.
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).
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:
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|
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.
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).
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[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/
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[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)