just_for_one's blog

Interesting string dp [maybe like digit dp]
By just_for_one, history, 3 years ago, In English

Question -

We are given 3 strings let say s1,s2,s3. s1 and s2 are of same length. We need to find the number of strings t of length = length of s1 or s2 (both are same) such that s1<=t<=s2 and t does not contain s3 as its substring.

My approach -

Initially, I am trying to precalculate $$$dp[i][j]$$$ as the number of strings of length n-i such that the prefix it has a prefix of length exactly j of string s3. here $$$0<=j<=len(s3)-1$$$, [Beacuse we cannot afford the original entire string as it is not allowed]. Here transitions are $$$dp[i][j]=dp[i+1][j-1]$$$, only for $$$dp[i][0]$$$ we need to place all characters and ensure it is not a suffix of $$$s3$$$.

Then I am doing normal digit dp type of thing, let's say we are at $$$i^th$$$ position in string s1, I am placing character c from s1[i]+1 to upto 'z' at $$$ith$$$ position to make it greater than s and checking for all prefix length x of s3 which can be placed at the $$$(i+1)^th$$$ position so that it do not form the original string $$$s3$$$, the only condition here is string $$$suffix(s1_{i-1},len(s3)-x-1)+char(k)+prefix(s3,x)$$$ must not be equal to $$$s3$$$. Then we can place it and add $$$dp[i+1][x]$$$ to our answer. Also at last if the original string ($$$s1$$$) satisfies this condition then add 1 to answer. Let this function be num.

Similarly do the same thing for $$$s2$$$.

Final answer is $$$num(s1)-num(s2)$$$+(s2 satisfies the condition) But it turns out that I am overcounting sometimes. Can anyone tell me if this method is incorrect or someone can suggest some better method?

It will be highly appreciated

Thanks

  • Vote: I like it
  • 0
  • Vote: I do not like it

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

Can you give the link to the problem , I think I have a solution and thus want to check it .

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

    There is no link. I have seen this somewhere in leetcode discuss, this is a hiring question of uber as far as I remember.

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

I suck at Digit DP but here is my try:

The DP state is $$$dp[i][oks1][oks2][pre]$$$ where:

  • $$$i$$$ means we have already chosen $$$i - 1$$$ letters
  • $$$oks1$$$ means there exist some indice $$$x < i$$$ that $$$s[x] > s1[x]$$$
  • $$$oks2$$$ means there exist some indice $$$x < i$$$ that $$$s[x] < s2[x]$$$
  • $$$pre$$$ means the length of the longest prefix of $$$s3$$$ end at $$$i$$$

The transitions:

  • Precalculate the array $$$next[len][c]$$$ means that the longest prefix of $$$s3$$$ end at $$$i$$$ after insert character $$$c$$$ and the longest prefix of $$$s3$$$ end at $$$i - 1$$$ has the length $$$len$$$. Just remember $$$next[n][c]$$$ with whatever $$$c$$$ is always $$$n$$$
  • Assume at indice $$$i$$$ we could chose the letter in range $$$[l, r]$$$, if:
    • $$$oks1$$$ then $$$l = 'a'$$$ otherwise $$$l = s1[i]$$$
    • $$$oks2$$$ then $$$r = 'z'$$$ otherwise $$$r = s2[i]$$$

  • For character $$$c$$$ calculate new value of $$$oks1$$$ and $$$oks2$$$ then we have the formula:

    $$$dp[i + 1][newOks1][newOks2][next[pre][c]] += dp[i][oks1][oks2][pre]$$$

And the answer is: $$$\sum_{k = 0}^{n-1} dp[n][0/1][0/1][k]$$$

Correct me if I'm wrong :3

→ Reply