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:

aa --> 1 (The only beautiful sub-sequence is empty sequence)
bccb --> 4 (we can get {bc,cb,cc,bb} so answer is 4)
bbbbbb --> 1 (the only possible sub-sequence is bbbb, so answer is 1)

hello__world_
5 years ago
6

Comments (4)

Show archived | Write comment?

Baynazar

5 years ago, hide # |

← Rev. 2 →

-10

1<=length(s)<=20

my code

include <bits/stdc++.h>

include <math.h>

typedef long long ll;

using namespace std;

ll i, j, t, a, n, m, b, c, d, f, g;

string s, s1, s2, s3, s4, myst;

int x[50];

set ss;

int main() { ios::sync_with_stdio(0); cin.tie(0);

cin>>s;
s1="";
for (a=0; a<s.length(); a++)
{
    s2="";
    for (b=a+1; b<s.length(); b++)
    {
       s3="";
       for (c=b+1; c<s.length(); c++) s3=s3+s[c];
       myst=s1;
       myst=myst+s2;
       myst=myst+s3;
       ss.insert(myst);
       s2=s2+s[b];
    }
    s1=s1+s[a];
}
cout<<ss.size()<<endl;

} /*

→ Reply

wxhtzdy

5 years ago, hide # ^ |

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

18o3

5 years ago, hide # |

Any way of confirming that the test is over.

→ Reply

tiasmondal

5 years ago, hide # |

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

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef long double ld;




int main()
{

ios_base::sync_with_stdio(NULL);  cin.tie(0); cout.tie(0);

string s;
cin>>s;
int i=0;
int n=s.size();
int dp[n][3];
memset(dp,0,sizeof(dp));
while(i<n)
{
    char c=s[i];
    int cnt=0;
    int x=i;
    while(s[i]==c)
    {
        ++cnt;
        ++i;
        if(i==n)
            break;
    }
    --i;
    if(cnt==1)
    {
        dp[i][1]=1+(x-1>=0?dp[x-1][1]:0);
        dp[i][2]=(x-1>=0?dp[x-1][1]:0)+(x-1>=0?dp[x-1][2]:0)-(x-2>=0?s[x-2]==c:0);
    }
    else
    {
         dp[i][1]=1+(x-1>=0?dp[x-1][1]:0);
        dp[i][2]=1+(x-1>=0?dp[x-1][1]:0)+(x-1>=0?dp[x-1][2]:0)-(x-2>=0?s[x-2]==c:0);
    }
    ++i;


}

/*set<string> st;
for(i=0;i<n;++i)
{
    for(int j=i+1;j<n;++j)
    {
        string s2=s.substr(0,i)+s.substr(i+1,j-1-(i+1)+1)+s.substr(j+1,n-1-(j+1)+1);
        st.insert(s2);

    }
}

cout<<dp[n-1][2]<<" "<<st.size()<<"\n";*/
cout<<dp[n-1][2];




return(0);
}

Do comment if something is wrong.

→ Reply