Binary Substituition CodeChef Solution

Problem – Binary Substituition CodeChef Solution

Chef has a binary string S. He can replace any occurrence of –

• 01 with a
• 10 with b
• 010 with ab
• 101 with ba

While doing these operations, Chef noticed that he can end up with different strings depending upon the order of application of the operations. Given the final string containing only a and b, Chef wants to know the number of possible strings he might have began with.

As the number of initial strings can be large, print the result modulo 998244353.

Input Format

• The first line of input will contain a single integer T, denoting the number of test cases.
• Each test case consists of a single line of input denoting S, the final string obtained after applying the operations.

Output Format

For each test case, output the number of original strings that can result in the final string mod 998244353.

Constraints

• 1≤T≤5⋅10^4
• 1≤∣S∣≤10^5
• The sum of |S| over all test cases won’t exceed 5⋅10^5.
• S consists of a and b only.

Sample 1:

Input:
3
ab
aa
abb
Output:
2
1
2

Explanation:

Test case 1: The binary strings that can result in the string ab are 0110 and 010.

• 0110: Replace the first two characters 01 with a and last two characters 10 with b. Thus, we get ab.
• 010: Replace the characters 010 with ab.

Test case 2: The only binary string that can result in the string aa is 0101. In 0101, we replace the first two characters with a and last two characters with a as well.

Test case 3: The binary strings that can result in the string abb are 011010 and 01010.

• 011010: Replace the first two characters 01 with a, next two characters 10 with b, and last two characters 10 with b. Thus, we get abb.
• 01010: Replace the characters 010 with ab and the characters 10 with b.

Binary Substituition CodeChef Solution in C++17

#include<bits/stdc++.h>
#define ll long long
int MOD = 998244353;
int main(){
    int t;  std::cin >> t;
    while(t--){
        std::string s;  std::cin >> s;
        int n = s.length();
        ll dp[n + 1];
        dp[n] = 1;
        for(int i = n - 1; i >= 0; --i){
            dp[i] = dp[i + 1] % MOD;
            if(i < n - 1 && s[i] != s[i + 1])
                dp[i] = (dp[i] + dp[i + 2]) % MOD;
        }
        std::cout << dp[0] << '\n';
    }
}

Binary Substituition CodeChef Solution in Pyth 3

S = {'a','b','ab','ba'}
for _ in range(int(input())):
    s = input()
    N = len(s)
    dp = [0]*N
    dp[0]=1
    for i in range(1,N):
        c1=dp[i-1]
        c2=0
        if (s[i-1:i+1] in S):
              if i-2<0:
                  c2=1
              else:
                c2=dp[i-2]
        dp[i]=(c1+c2)%998244353

    print (dp[-1]%998244353)
    

Binary Substituition CodeChef Solution in Java

/* package codechef; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
    
    
	public static void main (String[] args) throws java.lang.Exception
	{
	    /*
	        01 with a
            10 with b
            010 with ab
            101 with ba
	    */
		// your code goes here
		int mod = 998244353;
		Scanner sc = new Scanner(System.in);
		int test = sc.nextInt();
		for(int t=1;t<=test;t++){
		    String s = sc.next();
		    int n = s.length();
		    int dp[] = new int[n];
		    dp[0]=1;
		    if(n==1){
		        System.out.println(1);
		        continue;
		    }
		        
		    dp[1]=(s.charAt(1)==s.charAt(0))?1:2;
		    for(int i=2;i<n;i++){
		        if(s.charAt(i)==s.charAt(i-1))
		            dp[i] = dp[i-1];
		        else
		            dp[i] = (dp[i-1] + dp[i-2])%mod;
		    }
		    
		    System.out.println(dp[n-1]);

		}
	}
}

Binary Substituition CodeChef Solution Review:

In our experience, we suggest you solve this Binary Substituition CodeChef Solution and gain some new skills from Professionals completely free and we assure you will be worth it.

If you are stuck anywhere between any coding problem, just visit Queslers to get the Binary Substituition CodeChef Solution

Find on CodeChef

Conclusion:

I hope this Binary Substituition CodeChef Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.

This Problem is intended for audiences of all experiences who are interested in learning about Data Science in a business context; there are no prerequisites.

Keep Learning!

More Coding Solutions >>

LeetCode Solutions

Hacker Rank Solutions

CodeChef Solutions