Aayushi_Bhardwaj_Pataka's blog

Number of Shortest Supersequences
By Aayushi_Bhardwaj_Pataka, history, 6 years ago, In English

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.

  • Vote: I like it
  • -2
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Limit on the lengths?

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Anyone able to solve this?

→ Reply
»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    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.

    → Reply
»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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:

s[i+1] == t[j+1] => d[i+1][j+1] = min(d[i+1][j+1], d[i][j] + 1)

otherwise 


d[i+1][j] = min(d[i+1][j], d[i][j] + 1) and d[i][j+1] = min(d[i][j+1], d[i][j] + 1);

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)

→ Reply