Chef and Binary String | CodeChef

editorial
,
1

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)