Another Casual Coder

This was a problem that required me to literally sleep over it to come up with a solution. The way I was solving it had a time complexity of O(N*M*S) where N=50K, M=50 and S=10K, which becomes intractable. The way to speed it up then was to perform a binary search to find the next greater element given a certain number (in the case of the problem an index). Complexity reduced to O(N*M*Log(S)), which was doable. Code is down below, take a look, cheers, ACC.

Number of Matching Subsequences - LeetCode

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

public int NumMatchingSubseq(string s, string[] words)
{
 List[] list = new List[26];
 for (int i = 0; i < list.Length; i++) list[i] = new List();
 //O(n)
 for (int i = 0; i < s.Length; i++) { int index = (int)(s[i] - 'a'); list[index].Add(i); } //O(|words| * |word| * Log(|s|)) = 5000*50*5 = 1.3M int retVal = 0; foreach (string word in words) { int minIndex = -1; foreach (char c in word) { int index = (int)(c - 'a'); minIndex = FindMinIndexGreaterThanNumber(list[index], minIndex); if (minIndex == -1) { break; } } retVal = (minIndex != -1) ? retVal + 1 : retVal; } return retVal; } public int FindMinIndexGreaterThanNumber(List list, int number)
{
 if (list.Count == 0 || number>= list.Last()) return -1;
 int left = 0;
 int right = list.Count - 1;
 while (left < right) { int middle = (left + right) / 2; if (list[middle] == number) { if (middle + 1 < list.Count) return list[middle + 1]; else return -1; } else if (list[middle] < number) { left = middle + 1; } else { right = middle; } } if (list[left]> number) return list[left];
 else if (left + 1 < list.Count && list[left + 1]> number) return list[left + 1];
 return -1;
}