We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Number of Matching Subsequences

Difficulty: Medium

Problem Description

Given a string s and an array of strings words, return the number of words[i] that is a subsequence of s. A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

Key Insights

  • A subsequence can be formed by deleting some characters from the original string without reordering.
  • Efficiently checking if a word is a subsequence can be done using a two-pointer technique or binary search.
  • The problem can involve multiple words, requiring an efficient solution to process them collectively.
  • Using a hashmap to store the positions of characters in the string s can optimize the subsequence checking process.

Space and Time Complexity

Time Complexity: O(N + W * M), where N is the length of s, W is the number of words, and M is the average length of each word. Space Complexity: O(N), for storing character positions in hashmap.

Solution

To solve the problem, we can utilize a hashmap to store the indices of each character in the string s. For each word in the words array, we can check if it is a subsequence of s by using a two-pointer technique. One pointer traverses the string s, and the other traverses the current word. If we find all characters of the word in s in the correct order, then it is a subsequence.

Code Solutions

def numMatchingSubseq(s, words):
    from collections import defaultdict
    
    # Store the positions of each character in the string s
    char_positions = defaultdict(list)
    for index, char in enumerate(s):
        char_positions[char].append(index)
    
    def is_subsequence(word):
        current_position = -1
        for char in word:
            if char not in char_positions:
                return False
            # Find the next position of char in s that is greater than current_position
            positions = char_positions[char]
            # Binary search to find the first position greater than current_position
            left, right = 0, len(positions)
            while left < right:
                mid = (left + right) // 2
                if positions[mid] > current_position:
                    right = mid
                else:
                    left = mid + 1
            if left == len(positions):
                return False
            current_position = positions[left]
        return True
    
    count = 0
    for word in words:
        if is_subsequence(word):
            count += 1
            
    return count
← Back to All Questions