Make it Alternating (Codeforces 1879C)
Tags: Greedy, combinatorics

You are given a binary string $$$s$$$. A binary string is a string consisting of characters 0 and/or 1.You can perform the following operation on $$$s$$$ any number of times (even zero):  choose an integer $$$i$$$ such that $$$1 \le i \le |s|$$$, then erase the character $$$s_i$$$. You have to make $$$s$$$ alternating, i. e. after you perform the operations, every two adjacent characters in $$$s$$$ should be different.Your goal is to calculate two values:  the minimum number of operations required to make $$$s$$$ alternating;  the number of different shortest sequences of operations that make $$$s$$$ alternating. Two sequences of operations are different if in at least one operation, the chosen integer $$$i$$$ is different in these two sequences. 

Input: The first line contains one integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.Each test case consists of one line containing the string $$$s$$$ ($$$1 \le |s| \le 2 \cdot 10^5$$$). The string $$$s$$$ consists of characters 0 and/or 1 only.Additional constraint on the input:  the total length of strings $$$s$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$. 

Output: For each test case, print two integers: the minimum number of operations you have to perform, and the number of different shortest sequences of operations. Since the second number might be large, print its remainder modulo $$$998244353$$$.

Note: In the first test case of the example, the shortest sequences of operations are:  $$$[2]$$$ (delete the $$$2$$$-nd character);  $$$[3]$$$ (delete the $$$3$$$-rd character). In the second test case of the example, the shortest sequences of operations are:   $$$[2, 1]$$$ (delete the $$$2$$$-nd character, then delete the $$$1$$$-st character);  $$$[2, 2]$$$;  $$$[1, 1]$$$;  $$$[1, 2]$$$;  $$$[3, 1]$$$;  $$$[3, 2]$$$. In the third test case of the example, the only shortest sequence of operations is $$$[]$$$ (empty sequence).

Sample Inputs:
3
10010
111
0101

Sample Outputs:
1 2
2 6
0 1

Solution (Python):
import sys, math
input = sys.stdin.readline

def inp():
    return int(input())

def inlt():
    return list(map(int, input().split()))

def insr():
    s = input()
    return list(s[:len(s) - 1])

def invr():
    return map(int, input().split())
tt = inp()
for _ in range(tt):
    s = insr()
    myList = []
    curElem = s[0]
    curCount = 0
    for c in s:
        if c != curElem:
            curElem = c
            if curCount > 1:
                myList.append(curCount)
            curCount = 1
        else:
            curCount += 1
    if curCount > 1:
        myList.append(curCount)
    numWays = 1
    deletions = sum(myList) - len(myList)
    for num in myList:
        numWays = numWays * num % 998244353
    for i in range(2, deletions + 1):
        numWays = numWays * i % 998244353
    print(deletions, numWays)

Solution (Python):
def mod_factorial(n, mod=998244353):
    """"""
    factorial = 1
    for multiplier in range(n):
        factorial = factorial * (multiplier + 1) % mod
    return factorial

def c1879():
    t = int(input())
    for _ in range(t):
        s = input()
        monotone_lens = []
        current_char = s[0]
        current_len = 0
        for c in s:
            if c == current_char:
                current_len += 1
            else:
                monotone_lens.append(current_len)
                current_len = 1
                current_char = c
        monotone_lens.append(current_len)
        steps = len(s) - len(monotone_lens)
        permutations = 1
        for length in monotone_lens:
            permutations = permutations * length % 998244353
        permutations = permutations * mod_factorial(steps) % 998244353
        print(steps, permutations)
if __name__ == '__main__':
    c1879()

Solution (Python):
for _ in range(int(input())):
    s = input()
    MOD = 998244353
    operate = 0
    ans = cnt = 1
    prev = '#'
    for c in s:
        if c == prev:
            operate += 1
            cnt += 1
        else:
            ans = ans * cnt % MOD
            cnt = 1
        prev = c
    ans = ans * cnt % MOD
    for i in range(2, operate + 1):
        ans = ans * i % MOD
    print(f'{operate} {ans}')