Babaza Game

import string

st = list(input())
en = list(input())

def frm(l, i):
    try:
        l.remove(i)
    except: pass

def validr(st, en, chng, i):
    if i-1 in chng or i+1 in chng: return
    if st[i] == en[i]: return
    if i > 0 and en[i] == st[i-1]: return
    if i < len(st)-1 and en[i] == st[i+1]: return
    st[i] = en[i]
    chng.append(i)

print("".join(st))
while st != en:
    lst = st[:]
    chng = []

    for i in range(len(st)):
        if (((i>0 and en[i-1] == st[i])
            or (i < len(st)-1 and en[i+1] == st[i]))
            and (i-1 not in chng)):
            validr(st, en, chng, i)


    for i in range(len(st)):
        validr(st, en, chng, i)

    last = -4
    if st == lst:
        for i in range(len(st)):
            if last == i-1: continue
            if st[i] == en[i]: continue
            valid = list(string.ascii_uppercase)
            frm(valid, st[i-1])
            frm(valid, st[i+1])
            frm(valid, en[i-1])
            frm(valid, en[i+1])
            st[i] = valid[-1]

            last = i

    print("".join(st))

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

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: ACCEPTED