Prompt: Given a string s and an array of strings words, return the number of words[i] that is a subsequence of s.

Note: 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.

Example:

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".

Input: s = "dsahjpjauf", words = ["ahjpjau","ja","ahbwzgqnuk","tnmlanowax"]
Output: 2

Solution: One solution is to loop through all words. For each word, we can loop through the characters in string s in a reverse order and pop off all characters from the word that is seen in string s. The runtime for this is O(m x n) where m is the number of words and n is the length of the string.

A faster approach is to use binary search for the positions of the characters in each word and the position of the same characters in string s. First, we can save all the positions of the characters in string s. Why?

We can see that the positions of characters in string s should be in ascending order. Hence, if all characters in a word are mapped to a certain position for each characters in string s, then all the mapped positions of characters in a word should also be in ascending order.

For example: s = ‘abcded’ indices = {‘a’: [0], ‘b’: [1], ‘c’: [2], ‘d’: [3,5], ‘e’:[4]}

  1. If word = ‘acded’, we can maintain a variable called current_position = -1,
  2. Now, we look for position of ‘a’, pos = 0, current_position < pos, so current_position = pos = 0.
  3. Then, we look for position of ‘c’, pos = 2, current_position < pos, current_position = pos = 2.
  4. Then, we look for position of ‘d’, pos = 3 (we choose from left to right), current_position < pos, current_position = pos = 3.
  5. Then, we look for position of ‘e’, pos = 4, current_position < pos, current_position = pos = 4.
  6. Then, we look for position of ‘d’, pos = 3(we choose from left to right) , current_position >= pos, is there any other position of ‘d’? -> Yes, pos = 5, now current_position < pos, so current_position = pos = 5.

Now, we have found all the characters in word in the indices hashmap, and in increasing order of their indices. Hence return true.

  1. Now suppose, our word was ‘bb’ and current_position = -1.
  2. Then, we look for the position of ‘b’, pos = 1, current_position < pos, current_position = pos = 1.
  3. Then, we look again for the position of the second ‘b’, pos = 1, current_position >= pos, is there any other position of b? -> NO, so we did not find the desired subsequence, Hence return False.

This solution requires each word to loop through each character and search for a possible mapped position where it is greater than the current position of the last character. And the list of positions for each character are created by looping string s in a sequential order, we can use binary search to search for that possible mapped position.

The runtime for this faster solution would be O(m x log(n))** where m is the number of words and n is the length of string s.