結果

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

ソースコード

diff # 

def find_min_subsequence(S, T):
    # Step 1: Check if any character in S is not present in T
    t_set = set(T)
    candidates = []
    for c in S:
        if c not in t_set:
            candidates.append(c)
    if candidates:
        return min(candidates)
    
    # Step 2: Check if S is a subsequence of T
    def is_subsequence(s, t):
        i = j = 0
        len_s = len(s)
        len_t = len(t)
        while i < len_s and j < len_t:
            if s[i] == t[j]:
                i += 1
                j += 1
            else:
                j += 1
        return i == len_s
    
    if is_subsequence(S, T):
        return -1
    
    # Step 3: Binary search to find the minimal k
    low = 1
    high = len(S)
    answer = None
    while low <= high:
        mid = (low + high) // 2
        prefix = S[:mid]
        if is_subsequence(prefix, T):
            low = mid + 1
        else:
            answer = prefix
            high = mid - 1
    return answer

# Read input
S = input().strip()
T = input().strip()

result = find_min_subsequence(S, T)
print(result if result is not None else -1)
0