GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

Friday 7 October 2022

[Solution] Binary Substituition CodeChef Solution



Problem

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.

Solution Click Below:-  👉CLICK HERE👈
👇👇👇👇👇

Output Format

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

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

No comments:

Post a Comment