Number of Matching Subsequences

Problem Statement

The challenge is to find the count of strings within an array words that can be formed as a subsequence from a given string s. A subsequence in this context means you can derive a string by removing some or no characters from the string s without changing the order of the remaining characters. Importantly, each string within words must maintain its internal character order to be considered a valid subsequence of s.

Examples

Example 1

Input:

s = "abcde", words = ["a","bb","acd","ace"]

Output:

3

Explanation:

There are three strings in words that are a subsequence of s: "a", "acd", "ace".

Example 2

Input:

s = "dsahjpjauf", words = ["ahjpjau","ja","ahbwzgqnuk","tnmlanowax"]

Output:

2

Constraints

• 1 <= s.length <= 5 * 104
• 1 <= words.length <= 5000
• 1 <= words[i].length <= 50
• s and words[i] consist of only lowercase English letters.

Approach and Intuition

The task involves determining if each word in the words array is a subsequence of the string s. Let’s break down how we might approach finding a solution:

1. Understand Subsequence: For a string to be a subsequence of another, each character of the former should appear in the latter and in the same order, though not necessarily consecutively.

2. Iterative Comparison:

   • Iterate through each word in the words array. For each word, try to match it against s.
   • Use pointers or indices to trace the position in both the word and s. Move through s until all characters of the current word are found in order.

3. Counting:

   • For each word, if you can trace all characters in s while maintaining order, count it as a valid subsequence.
   • Keep a total count of such valid subsequences.

4. Efficiency Consideration:

   • Given the potential size of s and number of words, an efficient approach would be crucial.
   • Avoid re-checking any part of the s unnecessarily by using the dual-pointer technique that advances on s for comparisons and only resets for the next word in words.

5. Edge Cases:

   • Consider matching with a single character.
   • Handle cases where elements in words could be an empty string theoretically (not explicitly counter-indicated given constraints but good to consider).

By following this method, you systematically verify each word against s, ensuring computational efficiency and adherence to the subsequence definition.

Solutions

class Solution {
    public int matchSubsequences(String mainString, String[] wordList) {
        int count = 0;
        ArrayList<Node>[] bucketArray = new ArrayList[26];
        for (int i = 0; i < 26; ++i)
            bucketArray[i] = new ArrayList<Node>();
    
        for (String word : wordList)
            bucketArray[word.charAt(0) - 'a'].add(new Node(word, 0));
    
        for (char ch : mainString.toCharArray()) {
            ArrayList<Node> currentBucket = bucketArray[ch - 'a'];
            bucketArray[ch - 'a'] = new ArrayList<Node>();
    
            for (Node node : currentBucket) {
                node.index++;
                if (node.index == node.word.length()) {
                    count++;
                } else {
                    bucketArray[node.word.charAt(node.index) - 'a'].add(node);
                }
            }
            currentBucket.clear();
        }
        return count;
    }
}
    
class Node {
    String word;
    int index;
    
    public Node(String word, int idx) {
        this.word = word;
        index = idx;
    }
}