def solution(s):
    if "harker" in s:
        return 1
    return 0
    
T = int(input())
 
for _ in range(T):
    s = input()
    print(solution(s))

mod = int(1e9+7)
t = int(input())
for _ in range(t):
    ans = []
    n = int(input())
    w = []
    for i in range(n):
        a = input().split()
        if a[0] == "1":
            s = a[1]
            count = 1
            for j in range(1, len(s)):
                if s[j] != s[j-1]:
                    count += 1
                    count %= mod
            w.append([count, s[0], s[-1]])
            ans.append(count)
        else:
            for j in range(len(a)): a[j] = int(a[j])
            cur = w[a[2]-1][0]
            if a[1] == 1:
                ans.append(w[a[2]-1][0])
            else:
                for j in range(3, len(a)):
                    cur += w[a[j]-1][0]
                    if w[a[j-1]-1][2] == w[a[j]-1][1]: cur -= 1
                    cur %= mod
                ans.append(cur)
            w.append([cur, w[a[2]-1][1], w[a[-1]-1][-1]])
    print(' '.join(map(str, ans)))

How can we get the first character of $$$a$$$ to match the first character of $$$b$$$ in 2 operations?

Can we apply this to the remaining indices?

If we want to make $$$a_1$$$ match $$$b_1$$$, we can use the following procedure:

1. Find an $$$i$$$ such that $$$a_i = b_1$$$. After operating on index $$$i$$$, $$$a_n$$$ will equal $$$b_1$$$.
2. Operate on index $$$1$$$, which reverses the entire string. Now, we have that $$$a_1 = b_1$$$.

Similar logic follows for the other indices. In particular, if we already have $$$a_j = b_j$$$ for all $$$j \lt i$$$ and we want to get $$$a_i = b_i$$$, we do the following:

1. Find a $$$j \geq i$$$ such that $$$a_j = b_i$$$. Operate on index $$$j$$$.
2. Operate on index $$$i$$$.

We perform these pairs of operations at most $$$n$$$ times, so we use at most $$$2n$$$ operations in total, which is sufficient to solve the problem. Note that this also means that the transformation is possible iff the multisets of characters in $$$a$$$ and $$$b$$$ are equal.

def solution(N, a, b):
    sequences = []
    for i in range(N):        
        found = -1
        for j in range(i, N):
            if a[j] == b[i]:
                sequences.append(j + 1)
                sequences.append(i + 1)
                
                a = a[0:j] + "".join(reversed(a[j:]))
                a = a[0:i] + "".join(reversed(a[i:]))
                found = j
                break
        
        if found == -1:
            return -1
    
    return sequences
 
N = int(input())
a = input()
b = input()
 
ans = solution(N, a, b)
if ans == -1:
    print(-1)
else:
    l = len(ans)
    print(l)
    for i in range(l):
        print(ans[i])

With $$$b$$$ and $$$c$$$ fixed, how many $$$(a, d)$$$ pairs do you really have to check?

Let's fix $$$(b, c)$$$. If there are no options for $$$a$$$ or $$$d$$$, it's clearly impossible. Otherwise, if there are at least two options for either $$$a$$$ or $$$d$$$, it's always possible. If not, there is exactly one option for both $$$a$$$ and $$$d$$$, so we can just check this manually. Therefore, we do a constant amount of work for each $$$(b, c)$$$ pair, and the number of $$$(b, c)$$$ pairs is bounded by the number of edges. Therefore, the problem is solved in $$$\cal{O}(n + m)$$$.

Note: For ease of implementation, we can just find up to two candidates for both $$$a$$$ and $$$b$$$, then brute force all pairs.

import itertools
 
n, m = map(int, input().split())
g = [[] for _ in range(n + 1)]
edges = []
 
for _ in range(m):
    u, v = map(int, input().split())
    g[u].append(v)
    g[v].append(u)
    edges.append((u, v))
 
for (b, c) in edges:
    opt_a, opt_d = [], []
    for u in g[b]:
        if len(opt_a) > 1: break
        if u != c: opt_a.append(u)
    for u in g[c]:
        if len(opt_d) > 1: break
        if u != b: opt_d.append(u)
 
    for (a, d) in itertools.product(opt_a, opt_d):
        if a != d:
            print(a, b, c, d, sep="\n")
            quit()
print(-1)