hello__world_'s blog

Help Needed
By hello__world_, history, 5 years ago, In English

This question was asked in Infosys test (2022).

Wael has a sequence S. He found that the sub-sequences of S that are derived from S after deleting exactly two letters are considered as beautiful subsequences.

Given string S, your task is to find the number of different beautiful subsequences of S. Since the answer can be very large return it modulo 10^9 + 7.

Input Format:

The first line contains a string S, denoting the given sequence.

Constraints:

1 <= len(S) <= 10^6

Sample Input:

  1. aa --> 1 (The only beautiful sub-sequence is empty sequence)

  2. bccb --> 4 (we can get {bc,cb,cc,bb} so answer is 4)

  3. bbbbbb --> 1 (the only possible sub-sequence is bbbb, so answer is 1)

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

Comments Comments (4)
| Write comment?
»
5 years ago, hide # |
← Rev. 2  
Vote: I like it -10 Vote: I do not like it

1<=length(s)<=20

my code
→ Reply
  • »
    »
    5 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    That's not true, because if you have string abcab you can delete first or second "ab" so you can get "cab" or "abc".

    → Reply
»
5 years ago, hide # |
 
Vote: I like it +8 Vote: I do not like it

Any way of confirming that the test is over.

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

I will try to explain this step by step. Let $$$dp[i][j]$$$ denote the number of strings possible strings with $$$j$$$ characters deleted. Here $$$j \lt =2$$$.

consider a stretch of indices with similar characters let from $$$x^{th}$$$ to $$$i^{th}$$$ i.e we are considering all ranges of equal characters. If the string is "accb" then the equal stretches are 1 to 1, 2 to 3, 4 to 4.

We will update $$$dp[i][1]$$$ and $$$dp[i][2]$$$; for $$$dp[i][1]$$$ --> we can delete one single character from xth to ith character this contributes 1 to answer or do not delete anything then add $$$dp[x-1][1]$$$ to answer.

dp[i][1]= 1 + dp[x-1][1]

for $$$dp[i][2]$$$ --> we can delete 2 character from xth to ith character, this contributes 1 to answer or delete one character to add $$$dp[x-1][1]$$$ or do not delete anything then add $$$dp[x-1][2]$$$ to answer. There is a chance of duplication here if $$$(x-2)^{th}$$$ character is same, so subtract this.

dp[i][2]=(i-x+1>=2?1:0) + dp[x-1][1]+dp[x-1][2]-(s[x-2]==s[x])

The final answer is $$$dp[n-1][2]$$$;

Code

Do comment if something is wrong.

→ Reply