Babaza Game

s = input()
t = input()

def is_valid(x):
    n = len(x)
    if n == 1:
        return True
    for i in range(1,n):
        if x[i] == x[i - 1]:
            return False
    return True

def is_ok(cur, bef, aft):
    if bef != None and cur == bef:
        return False

    if aft != None and cur == aft:
        return False

    return True

print(s)
n = len(s)
while s != t:
    pos = []
    for i in range(n):
        if s[i] != t[i]:
            if len(pos) == 0:
                pos.append(i)
            else:
                if abs(pos[-1] - i) > 1:
                    pos.append(i)

    c = list(s)
    for p in pos:
        ok = True
        if 0 <= p - 1 and s[p - 1] == t[p]:
            ok = False
        if p + 1 < n and s[p + 1] == t[p]:
            ok = False

        if ok:
            c[p] = t[p]
            continue

        for kem in "ABCDEFGHIJKLMNOPQRSTUVWXYZ":
            bef = None
            aft = None
            if 0 <= i - 1:
                bef = s[i - 1]
            if i + 1 < n:
                aft = s[i + 1]
            if is_ok(kem, bef, aft):
                c[i] = kem

    s = ''.join(c)
    print(s)

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: TIME LIMIT EXCEEDED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: WRONG ANSWER