CHFBTR :- Editorial

Author :- Divyesh Srivastava

Tester :- Divyesh Srivastava

Editorialist :- Divyesh Srivastava

Pre-Requisites :- Dynammic Programming ( DP )

Solution

This problem can be easily solved by making a 1-D DP. If previous two characters are same, the result of current state is equal to sum of result of previous two states otherwise result of current state is same as previous state. So, dp[s.length()] will be our answer.

#include<bits/stdc++.h>

#define ll long long

using namespace std;

```
ll const mod = 1e9+7;
ll i,j;
int main()
{
string s;
cin>>s;
ll dp[s.length()+1];
dp[0]=1;
dp[1]=1;
for(i=2;i<=s.length();i++)
{
if((s[i-1]==s[i-2]) )
dp[i]=(dp[i-1]+dp[i-2])%mod;
else
dp[i]=dp[i-1];
}
cout<<dp[s.length()]%mod<<endl;
}
```

// Time Complexity :- O(n)