To solve this problem, we need to determine the minimum number of characters to delete from string A so that the resulting string becomes a subsequence of string B.

Approach

The key insight here is to find the longest subsequence of A that is also a subsequence of B. The minimum number of deletions required will be the length of A minus the length of this longest subsequence.

To efficiently find this longest subsequence, we preprocess string B to create a next_pos array. This array helps us quickly find the next occurrence of any character in B starting from a given position. Here's the detailed approach:

1. Preprocess B: Create a next_pos array where next_pos[i][c] (for character c and position i in B) gives the smallest index j >= i in B where character c is found. If no such index exists, it is set to -1.
2. Find Longest Subsequence: Using the next_pos array, iterate through string A and count how many characters of A can form a subsequence of B. This count gives the length of the longest valid subsequence.
3. Calculate Deletions: The minimum deletions required is the length of A minus the count of valid characters.

Solution Code

def min_deletions_to_subsequence(A, B):
    len_B = len(B)
    # next_pos[i][c] is the next index >= i in B where character c (0-25) is present
    next_pos = [[-1] * 26 for _ in range(len_B + 1)]

    for i in range(len_B - 1, -1, -1):
        # Copy the next state (i+1) to current state (i)
        next_pos[i] = next_pos[i+1][:]
        # Update the current character's position
        char_index = ord(B[i]) - ord('a')
        next_pos[i][char_index] = i

    current_pos = 0
    valid_count = 0

    for char in A:
        char_index = ord(char) - ord('a')
        pos = next_pos[current_pos][char_index]
        if pos != -1:
            valid_count += 1
            current_pos = pos + 1  # Move to next position in B

    return len(A) - valid_count

Explanation

1. Preprocessing B: The next_pos array is built by iterating B from the end to the beginning. For each position i, we copy the values from i+1 and then update the position of the current character to i. This allows us to quickly look up where the next occurrence of any character is in B from any starting position.
2. Finding Valid Subsequence: For each character in A, we use next_pos to find the next occurrence in B starting from our current position. If found, we increment the valid count and move our current position in B to the next index after the found character.
3. Result Calculation: The difference between the length of A and the valid count gives the number of characters we need to delete from A to make it a subsequence of B.

This approach efficiently handles large strings with a time complexity of O(len(B)*26 + len(A)), which is linear in the size of the input strings (since 26 is a constant for lowercase letters). This ensures the solution is optimal and scalable.

作者声明:本文包含人工智能生成内容。