結果

問題 No.1192 半部分列
ユーザー gew1fw
提出日時 2025-06-12 15:51:14
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,872 bytes
コンパイル時間 168 ms
コンパイル使用メモリ 82,108 KB
実行使用メモリ 53,956 KB
最終ジャッジ日時 2025-06-12 15:51:34
合計ジャッジ時間 4,008 ms
ジャッジサーバーID
(参考情報)
judge5 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 3 TLE * 1 -- * 21
権限があれば一括ダウンロードができます

ソースコード

diff #

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
    return i == len_s

def find_min_subsequence(S, T):
    set_T = set(T)
    # 情况一:检查S中是否有字符不在T中
    min_char = None
    for c in S:
        if c not in set_T:
            if min_char is None or c < min_char:
                min_char = c
    if min_char is not None:
        return min_char
    
    # 情况二:检查S是否是T的子序列
    if is_subsequence(S, T):
        return -1
    
    # 情况三:构造结果字符串
    result = []
    current_pos = 0
    n = len(S)
    while current_pos < n:
        min_c = None
        min_i = -1
        # 遍历从current_pos开始的所有字符,寻找最小的c,使得result + c 不是T的子序列
        for i in range(current_pos, n):
            c = S[i]
            temp_result = result + [c]
            if not is_subsequence(temp_result, T):
                if (min_c is None) or (c < min_c):
                    min_c = c
                    min_i = i
        # 如果找到符合条件的c
        if min_i != -1:
            result.append(S[min_i])
            current_pos = min_i + 1
        else:
            # 没有找到,选择current_pos处的字符,继续处理
            result.append(S[current_pos])
            current_pos += 1
            # 检查当前result是否满足条件
            if not is_subsequence(result, T):
                break
    # 检查最终的result是否满足条件
    if not is_subsequence(result, T):
        return ''.join(result)
    else:
        return -1

# 读取输入
S = input().strip()
T = input().strip()

# 处理特殊情况:S为空字符串的情况
if not S:
    print("")
else:
    res = find_min_subsequence(S, T)
    print(res)
0