In a palindrome, the first and last characters are equal, the second and second last characters are equal, ...

Since we are going to double every character, the size of the output will be twice of the original. So if we place a copy of the first character at the last index, the copy of the second character at the second last index, and continue like this, the result will be $$$s + reverse(s)$$$.

import sys
input = lambda: sys.stdin.readline().rstrip()

t = int(input())
for _ in range(t):
    s = input()
    
    s_reverse = s[::-1] 
    print(s + s_reverse)

We assume the answer is $$$x$$$. In its binary representation, one bit will be $$$1$$$ only if in all the $$$a_i$$$'s binary representation, this bit is $$$1$$$. Otherwise, we can use one operation to make this bit in $$$x$$$ become $$$0$$$, which is a smaller answer.

So we can set $$$x=a_1$$$ initially. Then we iterate over the sequence and make $$$x$$$=$$$x$$$ & $$$a_i$$$, the $$$x$$$ is the answer finally.

import sys

t = int(sys.stdin.readline().strip())

for _ in range(t):

    n = int(sys.stdin.readline().strip())

    nums = list(map(int, sys.stdin.readline().strip().split()))

    x = nums[0]

    for i in range(1, n):

        x &= nums[i]
        
    print(x)
    

A word $$$s$$$ of length $$$n$$$ being $$$k-complete$$$ occurs if and only if there exists a palindrome $$$t$$$ of length $$$k$$$ such that $$$s$$$ can be generated by several concatenations of $$$t$$$.

By systematically ensuring that all characters at positions $$$i, k-i+1, k+i, 2k-i+1, 2k+i, 3k-i+1, …$$$ for all $$$1≤i≤ k$$$ are equal in the final string, we can solve the problem independently for each $$$i$$$. To minimize the required number of changes, it's advisable to make all the letters equal to the one which appears at these positions the most initially. Calculate the maximum number of appearances and sum up overall $$$i$$$. However, be cautious with an odd $$$k$$$ because the letter in the center of each block has a different formula.

Time Complexity: $$$O(n)$$$ Space Complexity:$$$O(k)$$$

from sys import stdin
from collections import defaultdict, Counter

def main():
    for _ in range(int(input())):
        n, k = map(int, input().split())
        s = input()
        
        freq = defaultdict(Counter)
        for i in range(n):
            loc = min(i % k, k - i % k - 1)
            freq[loc][s[i]] += 1
        
        changes_needed = 0
        tot = 2 * (n // k)
        for i in range(k // 2):
            max_freq= max(freq[i].values())
            changes_needed += tot - max_freq
        
        if k % 2:
            max_freq = max(freq[k//2].values())
            changes_needed += n//k - max_freq
        
        print(changes_needed)


if __name__ == '__main__':
    main()

There should be at least one $$$b$$$ between consecutive $$$a$$$'s. Can't we just consider the last $$$b$$$ we have seen while iterating?

We don't need to do anything about characters other than $$$a$$$ and $$$b$$$.
When we encounter $$$b$$$ let's record how many valid sequences we have. So when we now encounter an $$$a$$$, the new $$$a$$$ can be appended to any of the sequences before the last $$$b$$$. Here the number of valid sequences increases by the amount we had before the last $$$b$$$ because we have the option to pick or not pick the current $$$a$$$. This new $$$a$$$ can also be a start of a new sequence, so we add 1 to the number of sequences we have so far.

• Time complexity: $$$O(n)$$$
• Space complexity: $$$O(1)$$$

import sys
input = lambda: sys.stdin.readline().rstrip()

mod = 10**9 + 7
s = input()

sequences = 0
before_last_b = 0 # the number of valid sequences before the last b

for idx, char in enumerate(s):
    if char == 'b':
        # all 'a's that come after now can immediately follow this 'b'
        # hence we can use all the valid sequences we have so far as prefixes of the next sequences we form
        before_last_b = sequences
    
    elif char == 'a':
        # this 'a' can be appended to sequences we formed before the last 'b' -> before_last_b
        # this character can also be a start of a new sequence, so we add 1
        sequences += before_last_b + 1
        sequences %= mod

print(sequences)

To solve this problem we need the prefix tree(trie), which will have all the strings from the group. Next we will calculate the two DP: $$$win[v]$$$ — Can player win if he makes a move now (players have word equal to prefix $$$v$$$ in the prefix tree(trie)). $$$lose[v]$$$ — Can player lose if he makes a move now (players have word equal to prefix $$$v$$$ in the prefix tree(trie)).

If $$$v$$$ is leaf of trie, then $$$win[v] = false$$$; $$$lose[v] = true$$$;

Else $$$win[v]$$$ = ($$$win[v]$$$ or (not $$$win[i]$$$)); $$$lose[v]$$$ = ($$$lose[v]$$$ or (not $$$lose[i]$$$)), such $$$i$$$ — children of vertex $$$v$$$.

Let's look at a few cases:

If $$$win[v] = false$$$, then second player win (first player lose all games).

If $$$win[v] = true$$$ and $$$lose[v] = true$$$, then first player win (he can change the state of the game in his favor).

If $$$win[v] = true$$$ and $$$lose[v] = false$$$, then if $$$k\ mod\ 2 = 1$$$, then first player win, else second player win.

Asymptotics — $$$O(\sum|s_i|)$$$.

import sys, threading
from sys import stdin

def input(): return stdin.readline().strip()

def main():
    N, K = map(int, input().split())

    root = {}

    def add(s):
        cur = root
        for ch in s:
            if ch not in cur:
                cur[ch] = {}
            cur = cur[ch]

    for _ in range(N):
        s = input()
        add(s)

    def get_winner(node): # Returns 1 (always wins), -1 (always loses) or 0 (wins or loses)
        can_win = False
        can_lose = False
        for ch in node:
            result = get_winner(node[ch])
            if result == 1:
                can_win = True
            elif result == -1:
                can_lose = True
            else:
                can_win = can_lose = True

        if can_win == False: # If my children always lose that means I can always win
            return 1
        elif can_lose == False: # If my children always win that means I can always lose
            return -1
        else:
            return 0

    first_can_win = False
    first_can_lose = False
    for ch in root:
        result = get_winner(root[ch])
        if result == 1:
            first_can_win = True
        elif result == -1:
            first_can_lose = True

    if first_can_win and (K%2 or first_can_lose):
        print("First")
    else:
        print("Second")

    
if __name__ == '__main__':
    
    sys.setrecursionlimit(1 << 30)
    threading.stack_size(1 << 27)

    main_thread = threading.Thread(target=main)
    main_thread.start()
    main_thread.join()