# BINARYSUB - Editorial

Author: Tejas Pandey
Tester: Harris Leung
Editorialist: Nishank Suresh

TBD

# PREREQUISITES:

Dynamic programming

# PROBLEM:

Given a binary string S, you can replace 01 with a, 10 with b, 010 with ab, and 101 with ba.

Given a string of a's and b's, how many initial strings could possibly have created this string?

# EXPLANATION:

We will use dynamic programming to find the answer.
Let A denote the input string.

Let dp_i denote the number of binary strings such that after replacement, they can form the first i characters of A. The answer we want is, of course, dp_N.

As a base case, we have dp_0 = 1, since we can only form the empty string from the empty string. Now, for i \geq 1:

• Suppose A_i = a. Then, we have two choices for a binary string that forms A_1A_2\ldots A_i
• If its last two characters were 01, we could replace them with a, then form the other i-1 characters from the remaining part of the string. There are dp_{i-1} ways to form the rest of the string.
• If its last three characters were 101 and A_{i-1} = b, we could replace 101 with ba and then form the remaining i-2 characters in dp_{i-2} ways. Note that this is only applicable when i \geq 2.
• There is no other way to obtain a string ending with a.
• The analysis for A_i = b will give you the exact same transitions.

So, our dp is as follows:

• dp_0 = 1
• For i \geq 1, dp_i = dp_{i-1}
• Further, if i \geq 2 and A_i \neq A_{i-1}, add dp_{i-2} to dp_i.

Finally, print dp_N.

# TIME COMPLEXITY

\mathcal{O}(N) per test case.

# CODE:

Editorialist's code (Python)
mod = 998244353
for _ in range(int(input())):
s = input()
n = len(s)
dp = [1]*(n+1)
for i in range(1, n):
dp[i+1] = dp[i]
if s[i] != s[i-1]:
dp[i+1] += dp[i-1]
dp[i+1] %= mod
print(dp[n])

1 Like

I solved it using Fibonacci sequence.

https://www.codechef.com/viewsolution/76392104

2 Likes

hey, I also applied the same logic but it didnâ€™t go well my code works great for small test cases but for large test cases my code output comes out to be 0 can you suggest something that I missed

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define ll long long
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define mii map<ll,ll>
#define pii pair<ll,ll>
#define vi vector<ll>
#define endl '\n'
#define REP(i,a,b) for(int i=a;i<b;i++)
#define input vi arr;REP(i,0,n){ll ele;cin>>ele;arr.pb(ele);}
void  solve(vi dp)
{
string arr;
cin>>arr;
ll result=1;
ll curr=1;
ll n=arr.size();
REP(i,0,n-1)
{
if(arr[i]!=arr[i+1])
{
curr++;
continue;
}
else
{
result*=dp[curr];
curr=1;
}
}
result*=dp[curr]%998244353;
cout<<result%998244353;
return ;
}
int main()
{
ll t;
cin>>t;
vi dp;
dp.pb(0);
dp.pb(1);
dp.pb(2);
REP(i,3,100001)
{
dp.pb((dp[i-1]+dp[i-2])%998244353);
}
while(t--)
{
solve(dp);
cout<<"\n";
}
return 0;
}


Fascinating approach, I almost understand it but am having some difficulty perhaps because I am not familiar with the language, could you please explain how the fibonacci sequence works for this problem.
Thank you.

Itâ€™s obvious that consecutive same lettes doesnâ€™t make new cases:
aaaaaaaaaa \to 1 possible construction of binary string.
ab\to 2 possible cases, and aaaaaabbbbbb \to 2 possible cases as well.

So itâ€™s optimal to consider these parts of string in blocks:
abababababababa\dots

Letâ€™s find how many different strings we can make up.
Letâ€™s consider a simple case - aba
Letâ€™s say if we replace ab with 010 we denote it like this \left\{ ab\right\}. And if we separetly replace a and b we denote it like this \left\{ a,b\right\}

So in case of aba , these cases are possible: \left\{ a,b,a\right\},\left\{ ab,a\right\}, \left\{ a,ba\right\} - 3 cases.
This way all the binary strings are distict.

To find solution for larger string (ababa\dots ) we have to make a simple observation.
Suppose we have abab\dots ab of length n.

Now letâ€™s consider all first positions where we pick ab or ba

\left\{a, b, a, b, \dots, a, b, a, b \right\}

Then the answer will be the sum of possible cases here:
\left\{ab, "abab..." (len = n-2)\right\}
\left\{a, ba, "baba..." (len = n-3)\right\}
\left\{a, b, ab, "abab..." (len = n-4)\right\}
and so on
\dots
\left\{a, b, a, b, \dots, a, b, "ab" \right\}
\left\{a, b, a, b, \dots, a, b, a, "b" \right\}

Here \left\{ a,b,a,\dots\right\} means that we already picked it and we donâ€™t consider them.
ababa... means that we consider possible cases this string can give.
If we denote the number of distinct binary strings ababa... with length k can give as f(k), the answer for ababa will be:

f(k-2)+f(k-3)+\dots +f(1)+f(0)+f(0)

The basic cases: f(0)=1, f(1)=1.
(Obviously, if we have "" or a there is only 1 way we can make up a binary string.

Then:

f(k)-f(k-1)=(f(k-2)+f(k-3)+\dots + f(1)+f(0)+f(0)) - (f(k-1)+f(k-3)+\dots+f(1)+f(0)+f(0))

f(k)-f(k-1)=f(k-2)

f(k)=f(k-1)+f(k-2)

Here we go!

But! We only considered some ababa substring of S.
The final answer to the problem is the product of all these f(k). Where k - length of some substring ababa\dots

We can simply precompute Fib array in O(10^5) and answer the queries in O(n)

2 Likes