Reverse and Concatenate (Codeforces 1634A)
Tags: Greedy, strings

Real stupidity beats artificial intelligence every time.— Terry Pratchett, Hogfather, DiscworldYou are given a string $$$s$$$ of length $$$n$$$ and a number $$$k$$$. Let's denote by $$$rev(s)$$$ the reversed string $$$s$$$ (i.e. $$$rev(s) = s_n s_{n-1} ... s_1$$$). You can apply one of the two kinds of operations to the string: replace the string $$$s$$$ with $$$s + rev(s)$$$ replace the string $$$s$$$ with $$$rev(s) + s$$$How many different strings can you get as a result of performing exactly $$$k$$$ operations (possibly of different kinds) on the original string $$$s$$$?In this statement we denoted the concatenation of strings $$$s$$$ and $$$t$$$ as $$$s + t$$$. In other words, $$$s + t = s_1 s_2 ... s_n t_1 t_2 ... t_m$$$, where $$$n$$$ and $$$m$$$ are the lengths of strings $$$s$$$ and $$$t$$$ respectively.

Input: The first line contains one integer $$$t$$$ ($$$1 \le t \le 100$$$) — number of test cases. Next $$$2 \cdot t$$$ lines contain $$$t$$$ test cases:The first line of a test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 100$$$, $$$0 \le k \le 1000$$$) — the length of the string and the number of operations respectively.The second string of a test case contains one string $$$s$$$ of length $$$n$$$ consisting of lowercase Latin letters.

Output: For each test case, print the answer (that is, the number of different strings that you can get after exactly $$$k$$$ operations) on a separate line.It can be shown that the answer does not exceed $$$10^9$$$ under the given constraints.

Note: In the first test case of the example:After the first operation the string $$$s$$$ can become either aabbaa or baaaab. After the second operation there are 2 possibilities for $$$s$$$: aabbaaaabbaa and baaaabbaaaab.

Sample Inputs:
4
3 2
aab
3 3
aab
7 1
abacaba
2 0
ab

Sample Outputs:
2
2
1
1

Solution (Python):
q = int(input())
for _ in range(q):
    (n, k) = map(int, input().split())
    s = input()
    if s == s[::-1] or k == 0:
        print(1)
    else:
        print(2)

Solution (Python):
t = int(input())
for _ in range(t):
    (n, k) = map(int, input().split())
    s = input()
    if s[::-1] == s or k == 0:
        print(1)
    else:
        print(2)

Solution (Python):
def pal(s):
    n = len(s)
    i = 0
    j = n - 1
    while i < j:
        if s[i] != s[j]:
            return False
        i += 1
        j -= 1
    return True
for _ in range(int(input())):
    (n, k) = list(map(int, input().split()))
    s = input()
    if k == 0:
        print(1)
    elif pal(s):
        print(1)
    else:
        print(2)