求使s2删除子串后成为s1子序列的最短删除子串长度

Alright, let's tackle this problem step by step. The core requirement here is to delete a single contiguous substring from s2 such that the remaining part becomes a subsequence of s1, and we need this deleted substring to be as short as possible.

Instead of focusing on what to delete, think about what to keep: we need the longest possible combination of a prefix of s2 (that's a subsequence of s1) plus a suffix of s2 (that's also a subsequence of s1), where the prefix ends before the suffix starts. The gap between them is the substring we can delete, and minimizing this gap's length is our goal.

We can break this down into three main steps:

1. Precompute left matching positions: Create an array left where left[i] is the last index in s1 that the substring s2[0..i] can reach as a subsequence.
2. Precompute right matching positions: Create an array right where right[i] is the first index in s1 that the substring s2[i..n-1] needs to start from to be a subsequence.
3. Find the minimal gap: Check all possible splits between prefix and suffix, plus edge cases (keeping only a prefix or only a suffix), to find the shortest contiguous substring that can be deleted.

def find_min_deletion_substring(s1, s2):
    m, n = len(s1), len(s2)
    if n == 0:
        return "", 0
    
    # Compute left array: left[i] = last index in s1 matched by s2[0..i]
    left = [-1] * n
    ptr = 0
    for i in range(n):
        if ptr < m and s2[i] == s1[ptr]:
            ptr += 1
        left[i] = ptr - 1
    
    # Compute right array: right[i] = first index in s1 needed for s2[i..n-1]
    right = [m] * n
    ptr = m - 1
    for i in range(n-1, -1, -1):
        if ptr >= 0 and s2[i] == s1[ptr]:
            ptr -= 1
        right[i] = ptr + 1
    
    min_delete_len = n  # Default: delete entire s2
    delete_start, delete_end = 0, n-1
    
    # Case 1: Keep only prefix s2[0..i], delete s2[i+1..n-1]
    for i in range(n):
        if left[i] >= 0:  # Prefix is valid subsequence
            current_len = n - (i + 1)
            if current_len < min_delete_len:
                min_delete_len = current_len
                delete_start = i + 1
                delete_end = n - 1
    
    # Case 2: Keep only suffix s2[j..n-1], delete s2[0..j-1]
    for j in range(n):
        if right[j] < m:  # Suffix is valid subsequence
            current_len = j
            if current_len < min_delete_len:
                min_delete_len = current_len
                delete_start = 0
                delete_end = j - 1
    
    # Case 3: Keep prefix s2[0..i] and suffix s2[j..n-1], delete s2[i+1..j-1]
    for i in range(n):
        for j in range(i + 1, n):
            if left[i] < right[j]:  # Prefix and suffix can connect in s1
                current_len = j - i - 1
                if current_len < min_delete_len:
                    min_delete_len = current_len
                    delete_start = i + 1
                    delete_end = j - 1
    
    # Handle edge case where keeping entire s2 is possible
    if left[-1] >= 0:
        return "", 0
    
    deleted_sub = s2[delete_start:delete_end + 1]
    return deleted_sub, min_delete_len

# Test Example 1
s1_example1 = "abbcabaa"
s2_example1 = "accbccbaa"
sub1, len1 = find_min_deletion_substring(s1_example1, s2_example1)
print(f"Example 1: Deleted substring is \"{sub1}\", length {len1}")

# Test Example 2
s1_example2 = "abcaacb"
s2_example2 = "adacaa"
sub2, len2 = find_min_deletion_substring(s1_example2, s2_example2)
print(f"Example 2: Deleted substring is \"{sub2}\", length {len2}")

Example 1 #

• s1 = "abbcabaa", s2 = "accbccbaa"
• The left array tells us that s2[0..1] ("ac") matches up to index 3 in s1, and s2[3..8] ("bbaa") starts matching from index 6 in s1. Since 3 < 6, we can delete the substring between them: s2[2..5] ("cbcc"), which is length 4. This leaves "acbaa", a valid subsequence of s1.

Example 2 #

• s1 = "abcaacb", s2 = "adacaa"
• The left array shows s2[0] ("a") matches index 0 in s1, and s2[2..5] ("acaa") starts matching from index 3 in s1. Since 0 < 3, we delete s2[1..2] ("da") with length 2. This leaves "acaa", which is a valid subsequence of s1.

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