Given two strings s and t. Find the number of ways to make a new string c such that both s and t appear as subsequences in c and also c has minimum length among all such strings possible.
I was able to figure out that the shortest length will be len(s) + len(t) — len(lcs(s, t)) but unable to approach further via any recursive/combinatorial approach.
Limit on the lengths?
O(n * m) or better would work where n and m are length of s and t respectively! (Hinting towards dp!?)
Anyone able to solve this?
Find the LCS (subsequence) of s and t and create the initial c = lcs(s, t). Now if we remove the LCS from s and t we will have length(lcs(s, t)) + 1 groups of characters which should be inserted before a certain letter in the inital c. Well then a simple construction would be to just add both 1-st groups before first letter of the the LCS (c), both 2-nd groups before the second letter and so on.
It doesn't work for s = "ab", t = "ba".
If c = lcs(s, t) = "a", the only answer you will find is "bab", though there are two answers.
d[i][j] = shortest length of string, such that it contains first i symbols of first string as subsequence, and first j symbols of the second string as a subsequence.
dp[i][j] = number of ways to build string with length d[i][j], such that it contains first i symbols of first string as subsequence, and first j symbols of the second string as a subsequence.
transitions:
otherwise
if transition in d is optimal (that means d[i+1][j] = d[i][j] + 1 and others), add ways to dp (dp[i+1][j] += dp[i][j] and others)