Scale Engineer

Number of Matching Subsequences

Med
#0746Time: O(W * N), where `W` is the number of words and `N` is the length of `s`. For each of the `W` words, we might scan the entire string `s` in the worst case.Space: O(1), as we only use a few variables for pointers, not counting the input storage.2 companies
Patterns
Dynamic Programming
Algorithms
Binary SearchSorting
Data structures
ArrayHash TableStringTrie
Companies
VisaSalesforce

Prompt

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.

  • For example, "ace" is a subsequence of "abcde".

 

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.

Approaches

3 approaches with complexity analysis and trade-offs.

This approach iterates through each word in the words array and, for each word, checks if it is a subsequence of the string s. This is the most straightforward but least efficient method, serving as a baseline.

Algorithm

  • Initialize a counter count to 0.
  • For each word in the words array:
    • Call a helper function isSubsequence(s, word) to check if word is a subsequence of s.
    • The helper function uses a two-pointer approach. One pointer i for s and another j for word.
    • It iterates through s with i. If s.charAt(i) matches word.charAt(j), it increments j.
    • If j reaches the end of word, it's a subsequence.
    • If the helper function returns true, increment count.
  • Return count.

Walkthrough

The core of this method is a helper function, isSubsequence(s, word), which determines if word is a subsequence of s. This function uses a two-pointer technique. One pointer traverses s, and the other traverses word. The pointer for word only advances when a matching character is found in s. If the word pointer reaches the end of the word, it means all its characters were found in s in the correct relative order, confirming it's a subsequence. The main function calls this helper for every word and counts the successes.

class Solution {    public int numMatchingSubseq(String s, String[] words) {        int count = 0;        for (String word : words) {            if (isSubsequence(s, word)) {                count++;            }        }        return count;    }     private boolean isSubsequence(String s, String word) {        int i = 0; // pointer for s        int j = 0; // pointer for word        while (i < s.length() && j < word.length()) {            if (s.charAt(i) == word.charAt(j)) {                j++;            }            i++;        }        return j == word.length();    }}

Complexity

Time

O(W * N), where `W` is the number of words and `N` is the length of `s`. For each of the `W` words, we might scan the entire string `s` in the worst case.

Space

O(1), as we only use a few variables for pointers, not counting the input storage.

Trade-offs

Pros

  • Simple to understand and implement.

  • Requires minimal extra memory.

Cons

  • Highly inefficient for the given constraints as it repeatedly scans the long string s.

  • Very likely to result in a "Time Limit Exceeded" (TLE) error on competitive programming platforms.

Solutions

class Solution {public  int numMatchingSubseq(String s, String[] words) {    Deque<int[]>[] d = new Deque[26];    Arrays.setAll(d, k->new ArrayDeque<>());    for (int i = 0; i < words.length; ++i) {      d[words[i].charAt(0) - 'a'].offer(new int[]{i, 0});    }    int ans = 0;    for (char c : s.toCharArray()) {      var q = d[c - 'a'];      for (int t = q.size(); t > 0; --t) {        var p = q.pollFirst();        int i = p[0], j = p[1] + 1;        if (j == words[i].length()) {          ++ans;        } else {          d[words[i].charAt(j) - 'a'].offer(new int[]{i, j});        }      }    }    return ans;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem