""" 多分想定解v1 """ import bisect def LIS(lis): seq = [] for c in lis: ind = bisect.bisect_left(seq,c) if ind == len(seq): seq.append(c) else: seq[ind] = c return len(seq) alp = "abcdefghijklmnopqrstuvwxyz?" cd = {} #文字→数字にする辞書型 for i in range(-1,26): cd[alp[i]] = i #N = int(input()) S = list(input()) #制約チェック #assert N == len(S) for i in S: assert i in cd N = len(S) #全て?の場合を処理する allq = True #全て?かどうかのフラグ for i in S: if i != "?": allq = False break if allq: print ("a"*N) sys.exit() # dp[i][c] = i文字目以降で作れる最長増加部分列のうち、c以上で始まる物の最長。?は無視する dpA = [[0] * 26 for i in range(N+1)] for i in range(N-1,-1,-1): nmax = 0 #dpA[i][c] の最大 (c > j) for j in range(25,-1,-1): dpA[i][j] = max(dpA[i+1][j] , nmax) if cd[S[i]] == j: dpA[i][j] = max(dpA[i][j] , nmax + 1) nmax = max(nmax , dpA[i][j]) OLIS = max(dpA[0]) #?を無視した際のLIS """ for i in dpA: print (*i) print (OLIS) """ ans = [] dpB = [[0] * 26 for i in range(N+1)] #i文字目以前で作れるLISのうち、c以下で終る物の最長 for i in range(N): if S[i] != "?": #?でない場合、置くものは一意 nc = cd[S[i]] else: #?の場合、置ける辞書順最小の物を探索する for c in range(26): if c == 0: if dpA[i+1][c+1] + 1 <= OLIS: nc = c break elif c != 25: if dpB[i-1][c-1] + dpA[i+1][c+1] + 1 <= OLIS: nc = c break else: #25 if dpB[i-1][c-1] + 1 <= OLIS: nc = c break else: print ("error",file=sys.stderr) sys.exit(1) ans.append(alp[nc]) nmax = 0 for j in range(26): dpB[i][j] = max(dpB[i-1][j] , nmax) if nc == j: dpB[i][j] = max(dpB[i][j] , nmax + 1) nmax = max(nmax , dpB[i][j]) assert LIS(ans) == OLIS print ("".join(ans))