PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: Tejas Pandey
Tester: Harris Leung
Editorialist: Nishank Suresh
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])