No Palindromes (Codeforces 1951E)
Tags: Greedy, hashing

Christopher Tin ft. Soweto Gospel Choir - Baba YetuඞYou are given a string $$$s$$$ consisting of lowercase Latin characters. You need to partition$$$^\dagger$$$ this string into some substrings, such that each substring is not a palindrome$$$^\ddagger$$$.$$$^\dagger$$$ A partition of a string $$$s$$$ is an ordered sequence of some $$$k$$$ strings $$$t_1, t_2, \ldots, t_k$$$, such that $$$t_1 + t_2 + \ldots + t_k = s$$$, where $$$+$$$ here represents the concatenation operation.$$$^\ddagger$$$ A string $$$s$$$ is considered a palindrome if it reads the same backwards as forwards. For example, $$$\mathtt{racecar}$$$, $$$\mathtt{abccba}$$$, and $$$\mathtt{a}$$$ are palindromes, but $$$\mathtt{ab}$$$, $$$\mathtt{dokibird}$$$, and $$$\mathtt{kurosanji}$$$ are not.

Input: Each test contains multiple test cases. The first line contains an integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.Each test case contains a string $$$s$$$ consisting of lowercase Latin characters ($$$1 \le |s| \le 10^6$$$).It is guaranteed that the sum of $$$|s|$$$ over all test cases does not exceed $$$10^6$$$.

Output: For each test case, print on one line "YES" if there exists a partition of $$$s$$$ whose parts are not palindromes, or "NO" if there is no such partition.If the answer is "YES", on the second line, print an integer $$$k$$$ — the number of parts that $$$s$$$ needs to be partitioned to such that each part is not a palindrome. On the third line, print $$$k$$$ strings $$$t_1, t_2, \ldots, t_k$$$ representing such a partition. If there are multiple such partitions, print any of them.

Note: In the first test case, since $$$\mathtt{sinktheyacht}$$$ is already non-palindrome, the partition $$$[\mathtt{sinktheyacht}]$$$ is valid.In the second test case, as any substring of the string $$$s$$$ is palindrome, there are no valid partitions.In the third test case, another valid partition is $$$[\mathtt{uw},\mathtt{uo}, \mathtt{wou}, \mathtt{wu}]$$$.

Sample Inputs:
3
sinktheyacht
lllllllll
uwuowouwu

Sample Outputs:
YES
1
sinktheyacht
NO
YES
3
uw uow ouwu

Solution (Python):
def pal(ch):
    if len(ch) % 2 == 0:
        x = len(ch) // 2
    else:
        x = len(ch) // 2 + 1
    if ch[:len(ch) // 2] == ch[x:][::-1]:
        return True
    else:
        return False

def tyco(ch):
    b = len(ch) // 2
    if len(ch) % 2 == 0:
        if pal(ch[:b]):
            a = 3
        else:
            a = 4
    elif pal(ch[:b]):
        a = 1
    else:
        a = 2
    return a
t = int(input())
for _ in range(t):
    s = input()
    T1 = True
    T2 = True
    a = 0
    x = 2
    if s == s[0] * len(s):
        T1 = False
    elif len(s) > 2 and s == s[:2] * (len(s) // 2) + s[0]:
        T1 = False
    if T1 and pal(s):
        if len(s) > 3:
            a = tyco(s)
        else:
            T1 = False
    if T1:
        if a == 0:
            s = [s]
            x = 1
        elif a == 1:
            z = len(s) // 2 + 1
            if s[z + 1:] == s[z + 1] * len(s[z + 1:]):
                T1 = False
            else:
                s = [s[:z + 1], s[z + 1:]]
        elif a == 2:
            z = len(s) // 2 + 1
            for k in range(len(s) // 2):
                if not (pal(s[z + k:]) or pal(s[:z + k])):
                    s = [s[:z + k], s[z + k:]]
                    T2 = False
                    break
            if T2:
                T1 = False
        elif a == 3:
            z = len(s) // 2
            s = [s[:z + 1], s[z + 1:]]
        else:
            z = len(s) // 2
            s = [s[:z], s[z:]]
        if T1:
            print('YES')
            print(x)
            print(' '.join(s))
        else:
            print('NO')
    else:
        print('NO')

Solution (Python):
def Palindrome(s) -> bool:
    return s == s[::-1]

def solve():
    s = input()
    (n, x) = (len(s), -1)
    if Palindrome(s[0:]) == False:
        print('YES')
        print(1)
        print(s)
        return
    for i in range(1, n):
        if s[i] != s[0]:
            x = i
            break
    if x == -1:
        print('NO')
        return
    if Palindrome(s[x + 1:]) == False:
        print('YES')
        print(2)
        print(s[:x + 1], ' ', s[x + 1:])
    elif x == 1 or x == n // 2:
        print('NO')
    else:
        print('YES')
        print(2)
        print(s[:x + 2], ' ', s[x + 2:])
for _ in range(int(input())):
    solve()

Solution (Python):
for _ in range(int(input())):
    s = input()
    if s != s[::-1]:
        print('YES\n1')
        print(s)
        continue
    z = -1
    for i in range(len(s) - 1, -1, -1):
        if s[i] != s[-1]:
            z = i
            break
    if z == -1:
        print('NO')
        continue
    if s[:z] != s[z - 1::-1]:
        print('YES\n2')
        print(s[:z], s[z:])
        continue
    if z == len(s) - 2:
        print('NO')
        continue
    if 2 * z + 1 == len(s):
        print('NO')
        continue
    print('YES\n2')
    print(s[:z - 1], s[z - 1:])