Problem:


Score : 500 points

Problem Statement

Snuke has a string s.
From this string, Anuke, Bnuke, and Cnuke obtained strings a, b, and c, respectively, as follows:

Choose a non-empty (contiguous) substring of s (possibly s itself). Then, replace some characters (possibly all or none) in it with ?s.

For example, if s is mississippi, we can choose the substring ssissip and replace its 1-st and 3-rd characters with ? to obtain ?s?ssip.

You are given the strings a, b, and c.
Find the minimum possible length of s.

Constraints

1 \leq |a|, |b|, |c| \leq 2000

a, b, and c consists of lowercase English letters and ?s.

Input

Input is given from Standard Input in the following format:

a
b
c

Output

Print the minimum possible length of s.

Sample Input 1

a?c
der
cod

Sample Output 1

7

For example, s could be atcoder.

Sample Input 2

atcoder
atcoder
???????

Sample Output 2

7

a, b, and c may not be distinct.



Sample input:
a?c
der
cod


Sample output:
7

Submission status: Time Limit Exceeded

Solution code:
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True  and False
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

def cmp1(a,b):
    l = []
    for i in range(len(a)):
        ok = True
        for j in range(min(len(b),len(a)-i)):
            #ddprint("a {} b {} i {} j {}".format(a,b,i,j))
            #ddprint("aij {} bj {}".format(a[i+j],b[j]))
            if a[i+j]!='?' and b[j]!='?' and a[i+j]!=b[j]:
                ok = False
                break
        if ok:
            l.append(i)
    #ddprint("cmp1 a {} b {} l {}".format(a,b,l))
    return l

def cmp(a,b):
    l1 = cmp1(a,b)
    l2 = cmp1(b,a)
    l2m = [-x for x in l2 if x!=0]
    l1.extend(l2m)
    return l1

a = ins()
b = ins()
c = ins()
la = len(a)
lb = len(b)
lc = len(c)
ab = cmp(a,b)
ac = cmp(a,c)
bc = cmp(b,c)
ddprint(ab)
ddprint(ac)
ddprint(bc)
ba = [-x for x in ab]
ca = [-x for x in ac]
cb = [-x for x in bc]
mn = la+lb+lc
for i in ab:
    for j in ac:
        if lc+j<=i or lb+i<=j or (j-i) in bc:
            v = max([la,lb+i,lc+j]) + max(0,-i,-j)
            mn = min(mn,v)
ddprint(mn)
for i in ba:
    for j in bc:
        if lc+j<=i or la+i<=j or (j-i) in ac:
            v = max([la+i,lb,lc+j]) + max(0,-i,-j)
            mn = min(mn,v)
ddprint(mn)
for i in ca:
    for j in cb:
        if lb+j<=i or la+i<=j or (j-i) in ab:
            v = max([la+i,lb+j,lc]) + max(0,-i,-j)
            mn = min(mn,v)
ddprint(mn)
for i in ab:
    v = max(la,lb+i)+max(0,-i)+lc
    mn = min(mn,v)
ddprint(mn)
for i in ac:
    v = max(la,lc+i)+max(0,-i)+lb
    mn = min(mn,v)
ddprint(mn)
for i in bc:
    v = max(lb,lc+i)+max(0,-i)+la
    mn = min(mn,v)
print(mn)

Submission status: Time Limit Exceeded

Solution code:
a = input()
b = input()
c = input()

def align(s1, s2):
    l1 = len(s1)
    l2 = len(s2)
    res = [s1 + s2]
    for i in range(l1):
        f = 0
        for j in range(min(l2, l1-i)):
            if s1[i+j] != s2[j] and s1[i+j] != '?' and s2[j] != '?':
                f = 0
                break
            else:
                f = 1
        if f:
            res.append(s1 + s2[j+1:])
    res.sort(key = lambda x:len(x))
    return res

cand = [[a, b, c], [a, c, b], [b, a, c], [b, c, a], [c, a, b], [c, b, a]]

res = 6000

for l in cand:
    tmp = align(l[0], l[1])
    for item in tmp:
        ans = align(item, l[2])
        res = min(res, len(ans[0]))

print(res)

Submission status: Time Limit Exceeded

Solution code:
a = input()
b = input()
c = input()

def match(c1, c2):
    return c1 == c2 or c1 == "?" or c2 == "?"

def check(x, y, xy):
    for i in range(len(x)):
        for j in range(len(y)):
            if not match(x[i], y[j]):
                xy[i - j + 50000] = True


l_a = len(a)
l_b = len(b)
l_c = len(c)

ab = [False] * 100000
ac = [False] * 100000
bc = [False] * 100000

check(a, b, ab)
check(a, c, ac)
check(b, c, bc)

l_max = 2000
ans = 3 * l_max
for i in range(-2 * l_max, 2 * l_max + 1):
    for j in range(-2 * l_max, 2 * l_max + 1):
        if not ab[i+50000] and not ac[j+50000] and not bc[j-i+50000]:
            lb = min(0, min(i, j))
            ub = max(l_a, max(l_b + i, l_c + j))
            ans = min(ans, ub - lb)
            
print(ans)

Submission status: Time Limit Exceeded

Solution code:
a = input()
b = input()
c = input()

def check(left, right):
    for i in range(len(left)):
        if(left[i] != "?" and right[i] != "?" and left[i] != right[i]):
            return False
    return True

def merge(left, right):
    ans = ""
    for i in range(len(left)):
        if(left[i] == "?"):
            ans += right[i]
        else:
            ans += left[i]
    return ans

def connect(left, right):
    ans = set()
    for i in range(len(left)):
        last_index = min(len(left), i + len(right))
        if(check(left[i:last_index], right[:last_index-i]) == True):
            tmp = []
            if(last_index < len(left)):
                tmp = left
            else:
                tmp = left[:i] + merge(left[i:last_index], right[:last_index-i]) + right[last_index-i:]
            ans.add(tmp)
    ans.add(left + right)
    return ans

ans = set()
tmp_ans = connect(a, b)
for t in tmp_ans:
    ans = ans | connect(t, c)
tmp_ans = connect(a, c)
for t in tmp_ans:
    ans = ans | connect(t, b)
tmp_ans = connect(b, a)
for t in tmp_ans:
    ans = ans | connect(t, c)
tmp_ans = connect(b, c)
for t in tmp_ans:
    ans = ans | connect(t, a)
tmp_ans = connect(c, a)
for t in tmp_ans:
    ans = ans | connect(t, b)
tmp_ans = connect(c, b)
for t in tmp_ans:
    ans = ans | connect(t, a)
ans

minAns = 99999
for an in ans:
    minAns = min(minAns, len(an))
print(minAns)

Submission status: Time Limit Exceeded

Solution code:
import sys
from itertools import permutations

a, b, c = sys.stdin.read().split()

def merge(s, t):
    n = len(s)
    m = len(t)
    cand = []
    for i in range(n):
        for j in range(min(m, n-i)):
            if s[i+j] != t[j]:
                if s[i+j] != '?' and t[j] != '?':
                    break
        else:
            if m >= n - i:
                cand.append(s[:i] + t)
            else:
                cand.append(s)
                break
    cand.append(s + t)
    return cand

def main():
    ans = 10000
    for p in permutations((a, b, c)):
        s, t, u = p
        cand = merge(s, t)
        for w in cand:
            res = merge(w, u)
            for r in res:
                ans = min(ans, len(r))
    return ans

if __name__ == "__main__":
    ans = main()
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import itertools

A,B,C = read().decode().split()

A = list(A)
B = list(B)
C = list(C)

def can_match(x,y):
    return x == '?' or y == '?' or x == y

M = 2020

def solve(A,B,C,LA,LB,LC):
    B_from_A = [False] * (M+M+1)
    for i in range(M+M+1):
        B_from_A[i] = all(can_match(x,y) for x,y in zip(A[i:],B))
    C_from_A = [False] * (M+M+1)
    for i in range(M+M+1):
        C_from_A[i] = all(can_match(x,y) for x,y in zip(A[i:],C))
    C_from_B = [False] * (M+M+1)
    for i in range(M+M+1):
        C_from_B[i] = all(can_match(x,y) for x,y in zip(B[i:],C))
    for i in range(M):
        if not B_from_A[i]:
            continue
        for j in range(i,i+M):
            if not C_from_A[j]:
                continue
            if not C_from_B[j-i]:
                continue
            yield max(LA, LB+i, LC+j)

answer = 10 ** 9
for A,B,C in itertools.permutations([A,B,C]):
    LA = len(A)
    LB = len(B)
    LC = len(C)
    x = min(solve(A,B,C,LA,LB,LC))
    if answer > x:
        answer = x
print(answer)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys

def getNextMin(a,b,bi,c):
    l = max(len(a)+1,bi+len(b)+1)
    for i in range(bi,l):
        match = True
        for j in range(len(c)):
            if c[j] == '?':
                continue
            if i+j < len(a) and a[i+j] != '?' and a[i+j] != c[j]:
                match = False
                break
            if i-bi+j < len(b) and b[i-bi+j] != '?' and b[i-bi+j] != c[j]:
                match = False
                break
        if match:
            return max(len(a),len(b)+bi,len(c)+i)
        # if match:
        #     substr = ""
        #     for k in range(bi):
        #         substr+=" "
        #     substr2 = ""
        #     for j in range(i):
        #         substr2+=" "
        #     r = max(len(a),len(b)+bi,len(c)+i)
        #     print(f"___MATCH___{bi}-{i}---->{r}")
        #     print(''.join(a))
        #     print(substr + ''.join(b))
        #     print(substr2 + ''.join(c))
        #     break
    

def getMin(a,b,c):
    m = 10**16
    for i in range(len(a)+1):
        match = True
        bi = i
        for j in range(len(b)):
            if i+j >=len(a):
                break
            if a[i+j] != '?' and b[j] != '?' and a[i+j] != b[j]:
                match = False
                break
        if match:
            m=min(m,getNextMin(a,b,bi,c))
    return m
            


def solve(a: str, b: str, c: str):
    a = list(a)
    b = list(b)
    c = list(c)
    print(min(getMin(a,b,c),getMin(a,c,b),getMin(b,c,a),getMin(b,a,c),getMin(c,a,b),getMin(c,b,a)))
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    a = next(tokens)  # type: str
    b = next(tokens)  # type: str
    c = next(tokens)  # type: str
    solve(a, b, c)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
a = input()
b = input()
c = input()

def check_two(x, y):
    keyi = []
    for i in range(len(x)):
        ok = True
        now = []
        for j in range(min(len(x[i:]),len(y))):
            if x[i + j] != y[j] and x[i + j] != "?" and y[j] != "?":
                ok = False
                now = []
                break
            else:
                if x[i + j] == "?":
                    now.append(y[j])
                else:
                    now.append(x[i + j])
        if ok == True:
            keyi.append(x[:i] + "".join(now) + y[j + 1:] + x[i + len(y):])
    return keyi + [x + y]

keyikeyi = []
for i in (check_two(a,b)):
    keyikeyi.extend(check_two(i, c))
for i in (check_two(a,c)):
    keyikeyi.extend(check_two(i, b))
for i in (check_two(b,c)):
    keyikeyi.extend(check_two(i, a))
for i in (check_two(b,a)):
    keyikeyi.extend(check_two(i, c))
for i in (check_two(c,a)):
    keyikeyi.extend(check_two(i, b))
for i in (check_two(c,b)):
    keyikeyi.extend(check_two(i, a))

miner = 10000000
for i in keyikeyi:
    miner = min(miner, len(i))

print(miner)


# s1 = check_two(check_two(a, b),c)
# s2 = check_two(check_two(a, c),b)
# s3 = check_two(check_two(b, a),c)
# s4 = check_two(check_two(b, c),a)
# s5 = check_two(check_two(c, b),a)
# s6 = check_two(check_two(c, a),b)
# print(s1,s2,s3,s4,s5,s6)
# print(min(len(s1),len(s2),len(s3),len(s4),len(s5),len(s6)))

Submission status: Time Limit Exceeded

Solution code:
stk = {}


def link(x,y): #x>=y前提。合うindを全列挙する

    nm = "".join(x) + "," + "".join(y)
    if nm in stk:
        return stk[nm]

    ret = []
    for i in range(len(x)):

        flag = True
        for j in range(len(y)):

            if j+i >= len(x):
                break

            if x[j+i] != y[j] and x[j+i] != "?" and y[j] != "?":
                flag = False
                break

        if flag:

            ret.append(i)

    for i in range(len(x),ddd+1):
        ret.append(i)

    
    stk[nm] = ret
    
    return ret




a = list(input())
b = list(input())
c = list(input())
ddd = len(a)+len(b)+len(c)

ans = float("inf")

nl = [[a,b,c],[a,c,b],[b,a,c],[b,c,a],[c,a,b],[c,b,a]]

for x,y,z in nl:

    xy = link(x,y)
    yz = link(y,z)
    xz = link(x,z)

    #print (x,y,z)
    #print (xy)
    #print (xz)
    #print (yz)
    
    dic = {}
    for i in yz:
        dic[i] = 1

    for j in xz:

        for i in xy:

            if i > j:
                break

            if j-i < len(y) and j-i not in yz:
                continue
            else:
                ans = min(ans , max(len(x) , len(y) + i , len(z) + j))
    
                
print (ans)       

        


"""
ans = min( len(link(link(a,b),c)) , len(link(link(a,c),b)) , len(link(link(b,a),c)) , len(link(link(b,c),a)) , len(link(link(c,a),b)) , len(link(link(c,b),a)))
ans = min(ans , len(link(c,link(a,b))) , len(link(b,link(a,c))) , len(link(c,link(b,a))) , len(link(a,link(b,c))) , len(link(b,link(c,a))) , len(link(a,link(c,b))))

print (ans)
"""

Submission status: Time Limit Exceeded

Solution code:
import sys
import itertools
a, b, c = [c for c in input()], [c for c in input()], [c for c in input()]
def sub2(xy, i, z, m):
    newm = max(len(xy), i + len(z))
    if newm >= m:
        return m
    for j in range(i, min(len(xy), i + len(z))):
        if xy[j] != z[j - i] and xy[j] != '?' and z[j - i] != '?':
            return m
    return newm
    
def sub1(x, y, i, z, m):
    if max(len(x), i + len(y), i + len(z)) >= m:
        return m
    xy = x + y[len(x) - i:]
    for j in range(i, min(len(x), i + len(y))):
        if x[j] != y[j - i]:
            if x[j] == '?':
                if y[j - i] != '?':
                    xy[j] = y[j - i]
            elif y[j - i] != '?':
                return m
    for k in range(i, len(xy)):
        m = sub2(xy, k, z, m)
    return m

def sub(x, y, z, m):
    for i in range(len(x) + 1):
        m = sub1(x, y, i, z, m)
    return m
m = len(a) + len(b) + len(c)
for x, y, z in itertools.permutations([a, b, c]):
    m = sub(x, y, z, m)
print(m)

Submission status: Time Limit Exceeded

Solution code:
a = input()
b = input()
c = input()

la = len(a)
lb = len(b)
lc = len(c)

AB = [False]*la
AC = [False]*la
BA = [False]*lb
BC = [False]*lb
CA = [False]*lc
CB = [False]*lc
for i in range(la):
    for s,t in zip(a[i:],b):
        if not(s=='?' or t=='?' or s==t):
            break
    else:
        AB[i] = True
for i in range(la):
    for s,t in zip(a[i:],c):
        if not(s=='?' or t=='?' or s==t):
            break
    else:
        AC[i] = True
for i in range(lb):
    for s,t in zip(b[i:],a):
        if not(s=='?' or t=='?' or s==t):
            break
    else:
        BA[i] = True
for i in range(lb):
    for s,t in zip(b[i:],c):
        if not(s=='?' or t=='?' or s==t):
            break
    else:
        BC[i] = True
for i in range(lc):
    for s,t in zip(c[i:],a):
        if not(s=='?' or t=='?' or s==t):
            break
    else:
        CA[i] = True
for i in range(lc):
    for s,t in zip(c[i:],b):
        if not(s=='?' or t=='?' or s==t):
            break
    else:
        CB[i] = True

ans = la+lb+lc
for i in range(-(lb+lc),la+max(lb,lc)+1):
    for j in range(-(lb+lc),la+max(lb,lc)+1):
        if 0<=i<la:
            ab = AB[i]
        elif -lb<i<0:
            ab = BA[-i]
        else:
            ab = True
        
        if 0<=j<la:
            ac = AC[j]
        elif -lc<j<0:
            ac = CA[-j]
        else:
            ac = True
            
        k = j-i
        if 0<=k<lb:
            bc = BC[k]
        elif -lc<k<0:
            bc = CB[-k]
        else:
            bc = True
        
        if ab and ac and bc:
            l = min(0,i,j)
            r = max(la,i+lb,j+lc)
            ans = min(ans,r-l)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    a = [c for c in input()]
    b = [c for c in input()]
    c = [c for c in input()]

    ans = 7000
    for x, y, z in [(a, b, c), (a, c, b), (b, a, c), (b, c, a), (c, a, b), (c, b, a)]:
        for m in cct(x, y):
            l = min(map(len, cct(m, z)))
            ans = min(ans, l)
    print(ans)


def cct(a, b):
    c = [a+b]
    for i in range(len(a)):
        z = list(a)
        f = True
        for j in range(len(b)):
            if i+j >= len(a):
                break
            elif a[i+j] != b[j]:
                if a[i+j] == '?':
                    z[i+j] = b[j]
                elif b[j] != '?':
                    f = False
                    break
        if f:
            if i+len(b) > len(a):
                z.extend(b[len(a)-i:])
            c.append(z)
    return c



main()

Submission status: Time Limit Exceeded

Solution code:
a = input()
b = input()
c = input()

def match(a, b, start):
    ret = [a + b]
    for i in range(start, len(a)):
        aa = a[i:]
        if len(aa) < len(b):
            bb = b[:len(aa)]
        else:
            aa = aa[:len(b)]
            bb = b

        f = True
        for j in range(len(aa)):
            if aa[j] != bb[j] and aa[j] != '?' and bb[j] != '?':
                f = False
                break
            elif aa[j] == '?' and bb[j] != '?':
                aa[j] == bb[j]
            elif aa[j] != '?' and bb[j] == '?':
                bb[j] == aa[j]
        if f:
            if len(a[i:]) < len(b):
                ret.append(a[:i] + b)
            else:
                ret.append(a)

    return ret

l = float('inf')
for seq in [(a, b, c), (a, c, b), (b, a, c), (b, c, a), (c, a, b), (c, b, a)]:
    ret1 = match(seq[0], seq[1], 0)
    for _ret1 in ret1:
        ret2 = match(_ret1, seq[2], 0)
        for _ret2 in ret2:
            l = min(l, len(_ret2))
print(l)

Submission status: Time Limit Exceeded

Solution code:
def solve(a, b, c):
    ans = 6000
    for line in get_merge_points(a, b, one_result=False):
        # print(line)
        ans = min(ans, list(get_merge_points(line, c, one_result=True))[0])
    return ans


def get_merge_points(base, ext, one_result=True):
    for point in range(len(base) + 1):
        flag = set()
        for i in range(point, min(len(base), point + len(ext))):
            if base[i] == ext[i - point]:
                '?? or aa'
                continue
            elif base[i] == 0 or ext[i - point] == 0:
                flag.add(i)
            else:
                break
        else:
            if one_result:
                yield max(len(base), point + len(ext))
                return
            if len(base) > point + len(ext):
                source = list(base)
            else:
                source = list(base)[:point] + list(ext)

            for f in flag:
                source[f] = base[f] if base[f] != 0 else ext[f - point]
            yield source


def convert(st):
    result = []
    for s in st:
        if s == '?':
            result.append(0)
        else:
            result.append(ord(s) - 90)
    return result


a = convert(input())
b = convert(input())
c = convert(input())

get_merge_points(a, b)

print(min(
    solve(a, b, c),
    solve(a, c, b),
    solve(b, a, c),
    solve(b, c, a),
    solve(c, a, b),
    solve(c, b, a)
))

Submission status: Time Limit Exceeded

Solution code:
def solve(a, b, c):
    ans = 60000
    for line in get_merge_points(a, b, one_result=False):
        # print(line)
        ans = min(ans, list(get_merge_points(line, c, one_result=True))[0])
    return ans


def get_merge_points(base, ext, one_result=True):
    for point in range(len(base) + 1):
        flag = set()
        for i in range(point, min(len(base), point + len(ext))):
            if base[i] == ext[i - point]:
                '?? or aa'
                continue
            elif base[i] == '?' or ext[i - point] == '?':
                flag.add(i)
            else:
                break
        else:
            if one_result:
                yield max(len(base), point + len(ext))
                return
            if len(base) > point + len(ext):
                source = list(base)
            else:
                source = list(base)[:point] + list(ext)

            for f in flag:
                source[f] = base[f] if base[f] != '?' else ext[f - point]
            yield source


a = input()
b = input()
c = input()

get_merge_points(a, b)

print(min(
    solve(a, b, c),
    solve(a, c, b),
    solve(b, a, c),
    solve(b, c, a),
    solve(c, a, b),
    solve(c, b, a)
))

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations

def equal(s, t):
    ret = [''] * len(s)
    for i in range(len(s)):
        if s[i] == '?':
            ret[i] = t[i]
        elif t[i] == '?' or s[i] == t[i]:
            ret[i] = s[i]
        else:
            return None
    return ret

def equal_rev(s, t):
    ret = [''] * len(s)
    for i in range(len(s)):
        j = len(s) - i - 1
        if s[j] == '?':
            ret[i] = t[i]
        elif t[i] == '?' or s[j] == t[i]:
            ret[i] = s[j]
        else:
            return None
    return ret

def join(s, t):
    ret = [s + t]
    for i in range(len(s) - len(t)):
        res = equal(s[i:i+len(t)], t)
        if res:
            ret.append(s[:i] + res + s[i+len(t):])

    s_right = []
    t_left = []
    for i in range(min(len(s), len(t))):
        j = len(s) - i - 1
        s_right.append(s[j])
        t_left.append(t[i])
        res = equal_rev(s_right, t_left)
        if res:
            ret.append(s[:j] + res + t[i+1:])
    return ret

a = list(input())
b = list(input())
c = list(input())

ans = float('inf')
for x, y, z in permutations([a, b, c]):
    xy = join(x, y)
    for s in xy:
        for t in join(s, z):
            ans = min(ans, len(t))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def solve(a, b, c):
    ans = 60000
    for line in get_merge_points(a, b):
        # print(line)
        x = list(get_merge_points(line, c))
        # print(x)
        ans = min(ans, min(map(len, x)))
    return ans

def get_merge_points(base, ext):
    for point in range(len(base) + 1):
        flag = set()
        for i in range(point, min(len(base), point + len(ext))):
            if base[i] == ext[i - point]:
                '?? or aa'
                continue
            elif base[i] == '?' or ext[i - point] == '?':
                flag.add(i)
            else:
                break
        else:
            if len(base) > point + len(ext):
                source = list(base)
            else:
                source = list(base)[:point] + list(ext)
            for f in flag:
                source[f] = base[f] if base[f] != '?' else ext[f - point]
            yield source


a = input()
b = input()
c = input()

get_merge_points(a, b)

print(min(
    solve(a, b, c),
    solve(a, c, b),
    solve(b, a, c),
    solve(b, c, a),
    solve(c, a, b),
    solve(c, b, a)
))

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations

def equal(s, t):
    ret = ''
    for i in range(len(s)):
        if s[i] == '?':
            ret += t[i]
        elif t[i] == '?' or s[i] == t[i]:
            ret += s[i]
        else:
            return ''
    return ret

def join(s, t):
    ret = [s + t]
    for i in range(len(s) - len(t)):
        res = equal(s[i:i+len(t)], t)
        if res:
            ret.append(s[:i] + res + s[i+len(t):])

    s_right = ''
    t_left = ''
    for i in range(min(len(s), len(t))):
        s_right = s[len(s)-i-1] + s_right
        t_left += t[i]
        res = equal(s_right, t_left)
        if res:
            ret.append(s[:len(s)-i-1] + res + t[i+1:])
    return ret


a = input()
b = input()
c = input()

ans = float('inf')
for x, y, z in permutations([a, b, c]):
    xy = join(x, y)
    for s in xy:
        for t in join(s, z):
            ans = min(ans, len(t))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
a = list(input())
b = list(input())
c = list(input())

import itertools
L = [a, b, c]

ans = len(a) + len(b) + len(c)

def nasu(x, y, z, ans):
  X = len(x)
  Y = len(y)
  for i in range(min(ans - Y, X)):
    for j in range(Y):
      if i + j >= X:
        ans = min(ans, honya(x, i, y, z, ans))
        break
      if x[i + j] != "?" and y[j] != "?":
        if x[i + j] != y[j]:
          break
    else:
      ans = min(ans, honya(x, i,y, z, ans))
  return ans

def honya(x, n, y, z, ans):
  k = max(len(x), n + len(y))
  X = len(x)
  Y = len(y)
  Z = len(z)
  for i in range(min(ans - Z, k)):
    for j in range(Z):
      if i + j >= k:
        ans = min(ans, i + Z)
        break
      if z[j] != "?":
        if i + j < X:
          if x[i + j] != "?" and x[i + j] != z[j]:
            break
        if i + j >= n and i + j < n + Y:
          if y[i + j - n] != "?" and y[i + j - n] != z[j]:
            break
    else:
      ans = min(ans, k)
      break
  return ans

for i in itertools.permutations([0, 1, 2]):
  x = L[i[0]]
  y = L[i[1]]
  z = L[i[2]]
  ans = min(ans, nasu(x, y, z, ans))

print(ans)

Submission status: Accepted

Solution code:
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))


"""
aを固定して，b，cの位置を全探索
"""
def main():
    mod=10**9+7
    a=input()
    b=input()
    c=input()
    M=2100

    
    def ch(c1,c2):
        return c1==c2 or c1=="?" or c2=="?"
    
    # aを左端に固定，bがbi文字目から,cが(bからみて)ci文字目から始まるとして，どうなるか
    # 実際にはabcの並びが6通り
    def calc(s1,s2,s3):
        
        # 遠く離れている場合などもokなので，初期値は1，ダメなら0に
        ab=[1]*(2*M)
        ac=[1]*(2*M)
        bc=[1]*(2*M)
        
        Na=len(s1)
        Nb=len(s2)
        Nc=len(s3)
        
        
        for bi in range(Na+5):#aの何文字目から?
            for j in range(Nb):#bの何文字目？
                if bi+j>=Na:
                    break
                if not ch(s1[bi+j], s2[j]):
                    ab[bi]=0
                    break
                
        for ci in range(Na+5):#aの何文字目から?
            for j in range(Nc):#cの何文字目？
                if ci+j>=Na:
                    break
                if not ch(s1[ci+j], s3[j]):
                    ac[ci]=0
                    break
                
        for ci in range(Nb+5):#bの何文字目から?
            for j in range(Nc):#cの何文字目？
                if ci+j>=Nb:
                    break
                if not ch(s2[ci+j], s3[j]):
                    bc[ci]=0
                    break
                
        ans=10**5
        for i in range(Na+5):#bの開始位置
            for j in range(i,Na+Nb+5):#cの開始位置
                if ab[i] and ac[j] and bc[j-i]:
                    temp=max(Na,i+Nb,j+Nc)
                    ans=min(ans,temp)
                    
        # print(ab)
        # print(ac)
        # print(bc)
                    
        return ans
    
    ans=len(a)+len(b)+len(c)
    
    ans=min(ans,calc(a,b,c))
    ans=min(ans,calc(a,c,b))
    ans=min(ans,calc(b,a,c))
    ans=min(ans,calc(b,c,a))
    ans=min(ans,calc(c,a,b))
    ans=min(ans,calc(c,b,a))
    
    print(ans)
                
            

main()

Submission status: Accepted

Solution code:
"""
a = 'a'*2000
b = 'b'*2000
c = 'c'*2000
"""
a = input()
b = input()
c = input()


len_a = len(a)
len_b = len(b)
len_c = len(c)

def match(a, b):
    return a=='?' or b=='?' or a==b

dp_len=50000
ab = [True] * dp_len
ac = [True] * dp_len
bc = [True] * dp_len

def check(a, b, ab):
    for i in range(len(a)):
        for j in range(len(b)):
            if not match(a[i], b[j]):
                ab[i-j+dp_len//2] = False

check(a, b, ab)
check(a, c, ac)
check(b, c, bc)

len_max = 2000

ans = len_a+len_b+len_c
for i in range(-2*len_max, 2*len_max+1):
    for j in range(-2*len_max, 2*len_max+1):
        if ab[i+dp_len//2] and ac[j+dp_len//2] and bc[j-i+dp_len//2]:
            ans = min(ans, max(len_a, len_b+i, len_c+j) - min(0, i, j))
print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations
ans = 6000
for a, b, c in permutations(input() for _ in range(3)):
    ab, bc, ac = [], [], []
    for s, t, st in [(a, b, ab), (b, c, bc), (a, c, ac)]:
        for i in range(len(s) + 1):
            for si, ti in zip(s[i:], t):
                if si != '?' and ti != '?' and si != ti:
                    st.append(False)
                    break
            else:
                st.append(True)
    for i in range(len(a) + 1):
        for j in range(max(len(b), len(a) - i) + 1):
            if ab[i] and (j > len(b) or bc[j]) and (i+j > len(a) or ac[i+j]):
                ans = min(ans, max(len(a), i+len(b), i+j+len(c)))
print(ans)