Qingshan Loves Strings (Codeforces 1890B)
Tags: Implement, constructive algorithms

Qingshan has a string $$$s$$$, while Daniel has a string $$$t$$$. Both strings only contain $$$\texttt{0}$$$ and $$$\texttt{1}$$$.A string $$$a$$$ of length $$$k$$$ is good if and only if  $$$a_i \ne a_{i+1}$$$ for all $$$i=1,2,\ldots,k-1$$$. For example, $$$\texttt{1}$$$, $$$\texttt{101}$$$, $$$\texttt{0101}$$$ are good, while $$$\texttt{11}$$$, $$$\texttt{1001}$$$, $$$\texttt{001100}$$$ are not good.Qingshan wants to make $$$s$$$ good. To do this, she can do the following operation any number of times (possibly, zero):  insert $$$t$$$ to any position of $$$s$$$ (getting a new $$$s$$$). Please tell Qingshan if it is possible to make $$$s$$$ good.

Input: The input consists of multiple test cases. The first line contains a single integer $$$T$$$ ($$$1\le T\le 2000$$$) — the number of test cases. The description of the test cases follows.The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n,m \le 50$$$) — the length of the strings $$$s$$$ and $$$t$$$, respectively.The second line of each test case contains a string $$$s$$$ of length $$$n$$$.The third line of each test case contains a string $$$t$$$ of length $$$m$$$.It is guaranteed that $$$s$$$ and $$$t$$$ only contain $$$\texttt{0}$$$ and $$$\texttt{1}$$$.

Output: For each test case, print "YES" (without quotes), if it is possible to make $$$s$$$ good, and "NO" (without quotes) otherwise.You can print letters in any case (upper or lower).

Note: In the first test case, $$$s$$$ is good initially, so you can get a good $$$s$$$ by doing zero operations.In the second test case, you can do the following two operations (the inserted string $$$t$$$ is underlined):  $$$\texttt{1}\underline{\texttt{010}}\texttt{11}$$$  $$$\texttt{10101}\underline{\texttt{010}}\texttt{1}$$$ and get $$$s = \texttt{101010101}$$$, which is good.In the third test case, there is no way to make $$$s$$$ good after any number of operations.

Sample Inputs:
5
1 1
1
0
3 3
111
010
3 2
111
00
6 7
101100
1010101
10 2
1001001000
10

Sample Outputs:
Yes
Yes
No
No
No

Solution (Python):
t = int(input())
for i in range(t):
    (n, m) = input().split()
    n = int(n)
    m = int(m)
    s = input()
    t = input()
    if '00' not in s and '11' not in s:
        print('yes')
    elif '00' in t or '11' in t:
        print('no')
    elif '00' in s and (t[0] == '0' or t[-1] == '0'):
        print('no')
    elif '11' in s and (t[0] == '1' or t[-1] == '1'):
        print('no')
    else:
        print('yes')

Solution (Python):
def is_good(s):
    for i in range(len(s) - 1):
        if s[i] == s[i + 1]:
            return False
    return True
sol = []
for j in range(int(input())):
    (n, m) = map(int, input().split())
    s = input()
    t = input()
    if n == 1 or is_good(s):
        sol.append('YES')
    elif not is_good(t):
        sol.append('NO')
    else:
        start = t[0]
        end = t[-1]
        flag = 1
        if '11' in s:
            if start == '1' or end == '1':
                sol.append('NO')
                flag = 0
        if flag:
            if '00' in s:
                if start == '0' or end == '0':
                    sol.append('NO')
                    flag = 0
        if flag:
            sol.append('YES')
for i in sol:
    print(i)

Solution (Python):
p = int(input())
res = []
while p:
    a = input().split()
    s = input()
    t = input()
    m = len(t)
    p -= 1
    if '00' not in s and '11' not in s:
        res.append('Yes')
    elif '00' in s and '11' not in s:
        if '00' not in t and '11' not in t and (t[0] == '1') and (t[m - 1] == '1'):
            res.append('Yes')
        else:
            res.append('No')
    elif '00' not in s and '11' in s:
        if '00' not in t and '11' not in t and (t[0] == '0') and (t[m - 1] == '0'):
            res.append('Yes')
        else:
            res.append('No')
    else:
        res.append('No')
print(*res, sep='\n')