Peculiar Movie Preferences (Codeforces 1628B)
Tags: Greedy, strings

Mihai plans to watch a movie. He only likes palindromic movies, so he wants to skip some (possibly zero) scenes to make the remaining parts of the movie palindromic.You are given a list $$$s$$$ of $$$n$$$ non-empty strings of length at most $$$3$$$, representing the scenes of Mihai's movie.A subsequence of $$$s$$$ is called awesome if it is non-empty and the concatenation of the strings in the subsequence, in order, is a palindrome.Can you help Mihai check if there is at least one awesome subsequence of $$$s$$$?A palindrome is a string that reads the same backward as forward, for example strings "z", "aaa", "aba", "abccba" are palindromes, but strings "codeforces", "reality", "ab" are not.A sequence $$$a$$$ is a non-empty subsequence of a non-empty sequence $$$b$$$ if $$$a$$$ can be obtained from $$$b$$$ by deletion of several (possibly zero, but not all) elements.

Input: The first line of the input contains a single integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases. The description of test cases follows.The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the number of scenes in the movie.Then follows $$$n$$$ lines, the $$$i$$$-th of which containing a single non-empty string $$$s_i$$$ of length at most $$$3$$$, consisting of lowercase Latin letters.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

Output: For each test case, print "YES" if there is an awesome subsequence of $$$s$$$, or "NO" otherwise (case insensitive).

Note: In the first test case, an awesome subsequence of $$$s$$$ is $$$[ab, cc, ba]$$$

Sample Inputs:
6
5
zx
ab
cc
zx
ba
2
ab
bad
4
co
def
orc
es
3
a
b
c
3
ab
cd
cba
2
ab
ab

Sample Outputs:
YES
NO
NO
YES
YES
NO

Solution (Python):
from sys import stdin, stdout

def next_line():
    return stdin.readline().rstrip()

def next_int():
    return int(next_line())

def out(text):
    stdout.write(str(text) + '\n')

def main():
    amount = next_int()
    for i in range(amount):
        word_amount = next_int()
        words = []
        for j in range(word_amount):
            words.append(next_line())
        out(solve(words, set(), set()))

def solve(words, all, additional):
    for word in words:
        l = len(word)
        reversed = word[::-1]
        if word[0] == word[-1] or reversed in all:
            return 'YES'
        all.add(word)
        if l == 2:
            if reversed in additional:
                return 'YES'
            continue
        last = reversed[:2]
        if last in all:
            return 'YES'
        additional.add(word[:2])
    return 'NO'
main()

Solution (Python):
""""""
import sys
input = sys.stdin.readline
R = lambda : map(int, input().split())
I = lambda : int(input())
S = lambda : input().rstrip('\n')
L = lambda : list(R())

def solve() -> str:
    n = I()
    s = [S() for _ in range(n)]
    st = set()
    st2 = set()
    if any((x[0] == x[-1] for x in s)):
        return 'YES'
    else:
        for x in s:
            if len(x) == 2 and x[::-1] in st:
                return 'YES'
            if len(x) == 3 and (x[::-1][:2] in st2 or x[::-1] in st2):
                return 'YES'
            st.add(x[:2])
            st2.add(x)
        return 'NO'
for _ in range(I()):
    print(solve())

Solution (Python):
from sys import stdin, stdout

def pr(out):
    return stdout.write(f'{out}\n')

def ver_in():
    return stdin.readline()

def hor_in():
    return list(map(int, stdin.readline().split()))

def solve():
    from collections import defaultdict
    n = int(ver_in())
    palindrome = False
    strings = []
    for i in range(n):
        ch = input()
        if ch == ch[::-1] or len(ch) == 1:
            palindrome = True
        strings.append(ch)
    dic3 = defaultdict(bool)
    dic2 = defaultdict(bool)
    dic32 = defaultdict(bool)
    if not palindrome:
        for i in range(n - 1, -1, -1):
            string = strings[i]
            if len(string) == 2:
                if dic2[string[::-1]]:
                    palindrome = True
                    break
                elif dic32[string[::-1]]:
                    palindrome = True
                    break
                dic2[string] = True
            else:
                if dic3[string[::-1]]:
                    palindrome = True
                    break
                elif dic2[string[:2][::-1]]:
                    palindrome = True
                    break
                dic32[string[1:]] = True
                dic3[string] = True
    if palindrome:
        pr('YES')
    else:
        pr('NO')
if __name__ == '__main__':
    t = int(ver_in())
    for _ in range(t):
        solve()