# PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

Contest: Division 3

Contest: Division 4

* Author:* Tejas Pandey

*Harris Leung*

**Tester:***Nishank Suresh*

**Editorialist:**# DIFFICULTY:

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])
```