Tandem Repeats? (Codeforces 1948D)
Tags: Others, two pointers

You are given a string $$$s$$$, consisting of lowercase Latin letters and/or question marks.A tandem repeat is a string of an even length such that its first half is equal to its second half.A string $$$a$$$ is a substring of a string $$$b$$$ if $$$a$$$ can be obtained from $$$b$$$ by the deletion of several (possibly, zero or all) characters from the beginning and several (possibly, zero or all) characters from the end.Your goal is to replace each question mark with some lowercase Latin letter in such a way that the length of the longest substring that is a tandem repeat is maximum possible.

Input: The first line contains a single integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of testcases.The only line of each testcase contains a string $$$s$$$ ($$$1 \le |s| \le 5000$$$), consisting only of lowercase Latin letters and/or question marks.The total length of the strings over all testcases doesn't exceed $$$5000$$$. 

Output: For each testcase, print a single integer — the maximum length of the longest substring that is a tandem repeat after you replace each question mark in the string with some lowercase Latin letter.If it's impossible to make any tandem repeat substrings in the string, print $$$0$$$.


Sample Inputs:
4
zaabaabz
?????
code?????s
codeforces

Sample Outputs:
6
4
10
0

Solution (Python):
def find_max_mirror_length(s):
    max_len = 0
    for sub_len in range(len(s) // 2, 0, -1):
        match_count = 0
        for i in range(len(s) - sub_len):
            if s[i] == s[i + sub_len] or s[i] == '?' or s[i + sub_len] == '?':
                match_count += 1
                if match_count == sub_len:
                    max_len = max(max_len, sub_len)
                    break
            else:
                match_count = 0
    return max_len

def main():
    test_cases = int(input())
    for _ in range(test_cases):
        s = input()
        ans = find_max_mirror_length(s)
        print(ans * 2)
if __name__ == '__main__':
    main()

Solution (Python):
def longestTandemRepeatedSubstring(str):
    n = len(str)
    for l in range(n // 2, 0, -1):
        matched = 0
        for i in range(l, n):
            if str[i - l] == '?' or str[i] == '?' or str[i - l] == str[i]:
                matched += 1
                if matched == l:
                    return matched * 2
            else:
                matched = 0
    return 0
for _ in range(int(input())):
    print(longestTandemRepeatedSubstring(input()))

Solution (Python):
t = int(input())

def solve():
    s = list(input())
    n = len(s)
    for j in range(n // 2, 0, -1):
        count = 0
        for k in range(0, n - j):
            if s[k] == '?' or s[k + j] == '?' or s[k] == s[k + j]:
                count += 1
            else:
                count = 0
            if count == j:
                print(count * 2)
                return
    print(0)
for i in range(t):
    solve()