如何筛选字符串中无法构成目标非连续子序列的元素？

问题分析 #

你需要判断字符串s1中的每个字符是否能参与构成s2的非连续子序列，输出对应的0/1标记（1表示可参与，0表示不可参与），且要求时间复杂度不高于O(N)。

高效解法思路 #

核心逻辑是：一个字符s1[i]能被用到，当且仅当存在s2中的某个位置j，使得s1[i] = s2[j]，且：

1. s1[0..i-1]能匹配s2的前j个字符（即s2[0..j-1]是s1[0..i-1]的子序列）；
2. s1[i+1..n-1]能匹配s2的从j+1开始的后缀（即s2[j+1..m-1]是s1[i+1..n-1]的子序列）。

基于此，我们可以通过两次线性遍历预处理出两个辅助数组，再通过一次遍历生成结果：

算法步骤 #

1. 预处理s2字符索引：
   创建字典记录s2中每个字符对应的所有索引（按升序排列），方便快速查找字符在s2中的位置。

2. 计算prefix数组：
   prefix[i]表示s1[0..i]能匹配s2的最长前缀长度（即s2[0..prefix[i]-1]是s1[0..i]的子序列），通过从左到右遍历s1生成。

3. 计算suffix数组：
   suffix[i]表示s1[i..n-1]能匹配s2的后缀起始索引（即s2[suffix[i]..m-1]是s1[i..n-1]的子序列），通过从右到左遍历s1生成。

4. 生成结果数组：
   遍历s1的每个字符，结合prefix和suffix数组判断该字符是否满足参与子序列的条件，标记对应结果。

代码实现（Python） #

def mark_usable_chars(s1, s2):
    n = len(s1)
    m = len(s2)
    if m == 0:
        return [0] * n
    
    # 预处理s2中每个字符的索引列表
    char_indices = {}
    for idx, c in enumerate(s2):
        if c not in char_indices:
            char_indices[c] = []
        char_indices[c].append(idx)
    
    # 计算prefix数组：s1[0..i]能匹配s2的前prefix[i]个字符
    prefix = [0] * n
    current_match = 0
    for i in range(n):
        c = s1[i]
        if current_match < m and c == s2[current_match]:
            current_match += 1
        prefix[i] = current_match
    
    # 计算suffix数组：s1[i..n-1]能匹配s2从suffix[i]开始的后缀
    suffix = [m] * (n + 1)
    current_match = m - 1
    for i in range(n-1, -1, -1):
        c = s1[i]
        if current_match >= 0 and c == s2[current_match]:
            current_match -= 1
        suffix[i] = current_match + 1
    
    # 生成结果
    result = [0] * n
    for i in range(n):
        c = s1[i]
        if c not in char_indices:
            continue
        # 检查该字符在s2中的所有可能位置
        for j in char_indices[c]:
            # 处理i=0的边界情况，prefix[-1]视为0
            prev_prefix = prefix[i-1] if i > 0 else 0
            # 前面能匹配到j个字符，后面能匹配j+1及以后的部分
            if prev_prefix >= j and suffix[i+1] <= j + 1:
                result[i] = 1
                break  # 只要有一个符合条件的j就标记为1
    
    return ' '.join(map(str, result))

# 测试示例
s1 = "123625421454"
s2 = "254"
print(mark_usable_chars(s1, s2))  # 输出：0 1 0 0 1 1 1 1 0 1 1 1

复杂度分析 #

• 预处理s2：O(m)
• 计算prefix数组：O(n)
• 计算suffix数组：O(n)
• 生成结果：O(n + k)（k为s1中属于s2的字符总出现次数，最多为n）
• 整体时间复杂度：O(n + m)，完全满足高效要求。

内容的提问来源于stack exchange，提问作者user16401948