結果

問題 No.1192 半部分列
ユーザー gew1fw
提出日時 2025-06-12 13:48:52
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,486 bytes
コンパイル時間 184 ms
コンパイル使用メモリ 82,732 KB
実行使用メモリ 105,620 KB
最終ジャッジ日時 2025-06-12 13:49:07
合計ジャッジ時間 3,422 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 10 WA * 15
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def main():
    S = sys.stdin.readline().strip()
    T = sys.stdin.readline().strip()

    # Preprocess T for subsequence check
    n = len(T)
    next_t = [[n] * 26 for _ in range(n + 1)]
    for i in range(n - 1, -1, -1):
        for c in range(26):
            next_t[i][c] = next_t[i + 1][c]
        char_code = ord(T[i]) - ord('a')
        next_t[i][char_code] = i

    # Check if S is a subsequence of T
    current_pos = 0
    is_subseq = True
    for c in S:
        code = ord(c) - ord('a')
        current_pos = next_t[current_pos][code]
        if current_pos >= n:
            is_subseq = False
            break
        current_pos += 1

    if not is_subseq:
        print(S)
        return

    # Check if S contains any character not in T
    t_chars = set(T)
    min_char = None
    min_pos = float('inf')
    s_has_char_not_in_t = False
    for i, c in enumerate(S):
        if c not in t_chars:
            s_has_char_not_in_t = True
            if min_char is None or c < min_char or (c == min_char and i < min_pos):
                min_char = c
                min_pos = i

    if s_has_char_not_in_t:
        print(min_char)
        return

    # Preprocess S for next character positions
    m = len(S)
    next_pos_s = [[-1] * 26 for _ in range(m + 1)]
    last = [-1] * 26
    for i in range(m - 1, -1, -1):
        c_code = ord(S[i]) - ord('a')
        last[c_code] = i
        for j in range(26):
            next_pos_s[i][j] = last[j]

    # Find the minimal candidate of length 2
    min_candidate = None
    for i in range(m):
        c1 = S[i]
        code1 = ord(c1) - ord('a')
        # Check each possible c2 in order a-z
        for code2 in range(26):
            j = next_pos_s[i + 1][code2]
            if j == -1:
                continue
            # Check if c1 followed by c2 is not a subsequence of T
            pos = next_t[0][code1]
            if pos >= n:
                candidate = c1 + chr(code2 + ord('a'))
                if (min_candidate is None) or (candidate < min_candidate):
                    min_candidate = candidate
                break
            pos_c2 = next_t[pos + 1][code2]
            if pos_c2 >= n:
                candidate = c1 + chr(code2 + ord('a'))
                if (min_candidate is None) or (candidate < min_candidate):
                    min_candidate = candidate
                break

    print(min_candidate if min_candidate is not None else -1)

if __name__ == '__main__':
    main()
0