Off-by-one on range boundaries
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Move from brute-force thinking to an efficient approach using array strategy.
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.
"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 * 1041 <= words.length <= 50001 <= words[i].length <= 50s and words[i] consist of only lowercase English letters.Problem summary: 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".
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Array · Hash Map · Binary Search · Dynamic Programming · Trie
"abcde" ["a","bb","acd","ace"]
"dsahjpjauf" ["ahjpjau","ja","ahbwzgqnuk","tnmlanowax"]
is-subsequence)shortest-way-to-form-string)count-vowel-substrings-of-a-string)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #792: Number of Matching Subsequences
class Solution {
public int numMatchingSubseq(String s, String[] words) {
Deque<String>[] d = new Deque[26];
Arrays.setAll(d, k -> new ArrayDeque<>());
for (String w : words) {
d[w.charAt(0) - 'a'].add(w);
}
int ans = 0;
for (char c : s.toCharArray()) {
var q = d[c - 'a'];
for (int k = q.size(); k > 0; --k) {
String t = q.pollFirst();
if (t.length() == 1) {
++ans;
} else {
d[t.charAt(1) - 'a'].offer(t.substring(1));
}
}
}
return ans;
}
}
// Accepted solution for LeetCode #792: Number of Matching Subsequences
func numMatchingSubseq(s string, words []string) (ans int) {
d := [26][]string{}
for _, w := range words {
d[w[0]-'a'] = append(d[w[0]-'a'], w)
}
for _, c := range s {
q := d[c-'a']
d[c-'a'] = nil
for _, t := range q {
if len(t) == 1 {
ans++
} else {
d[t[1]-'a'] = append(d[t[1]-'a'], t[1:])
}
}
}
return
}
# Accepted solution for LeetCode #792: Number of Matching Subsequences
class Solution:
def numMatchingSubseq(self, s: str, words: List[str]) -> int:
d = defaultdict(deque)
for w in words:
d[w[0]].append(w)
ans = 0
for c in s:
for _ in range(len(d[c])):
t = d[c].popleft()
if len(t) == 1:
ans += 1
else:
d[t[1]].append(t[1:])
return ans
// Accepted solution for LeetCode #792: Number of Matching Subsequences
struct Solution;
impl Solution {
fn num_matching_subseq(s: String, words: Vec<String>) -> i32 {
let mut queues: Vec<Vec<_>> = vec![vec![]; 26];
let mut temp: Vec<(char, _)> = vec![];
for word in &words {
let mut iter = word.chars();
if let Some(c) = iter.next() {
queues[(c as u8 - b'a') as usize].push(iter);
}
}
let mut res = 0;
for c in s.chars() {
let iters = &mut queues[(c as u8 - b'a') as usize];
while let Some(mut iter) = iters.pop() {
if let Some(d) = iter.next() {
temp.push((d, iter));
} else {
res += 1;
}
}
while let Some((c, iter)) = temp.pop() {
queues[(c as u8 - b'a') as usize].push(iter);
}
}
res
}
}
#[test]
fn test() {
let s = "abcde".to_string();
let words = vec_string!["a", "bb", "acd", "ace"];
let res = 3;
assert_eq!(Solution::num_matching_subseq(s, words), res);
}
// Accepted solution for LeetCode #792: Number of Matching Subsequences
// Auto-generated TypeScript example from java.
function exampleSolution(): void {
}
// Reference (java):
// // Accepted solution for LeetCode #792: Number of Matching Subsequences
// class Solution {
// public int numMatchingSubseq(String s, String[] words) {
// Deque<String>[] d = new Deque[26];
// Arrays.setAll(d, k -> new ArrayDeque<>());
// for (String w : words) {
// d[w.charAt(0) - 'a'].add(w);
// }
// int ans = 0;
// for (char c : s.toCharArray()) {
// var q = d[c - 'a'];
// for (int k = q.size(); k > 0; --k) {
// String t = q.pollFirst();
// if (t.length() == 1) {
// ++ans;
// } else {
// d[t.charAt(1) - 'a'].offer(t.substring(1));
// }
// }
// }
// return ans;
// }
// }
Use this to step through a reusable interview workflow for this problem.
Check every element from left to right until we find the target or exhaust the array. Each comparison is O(1), and we may visit all n elements, giving O(n). No extra space needed.
Each comparison eliminates half the remaining search space. After k comparisons, the space is n/2ᵏ. We stop when the space is 1, so k = log₂ n. No extra memory needed — just two pointers (lo, hi).
Review these before coding to avoid predictable interview regressions.
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Wrong move: Zero-count keys stay in map and break distinct/count constraints.
Usually fails on: Window/map size checks are consistently off by one.
Fix: Delete keys when count reaches zero.
Wrong move: Setting `lo = mid` or `hi = mid` can stall and create an infinite loop.
Usually fails on: Two-element ranges never converge.
Fix: Use `lo = mid + 1` or `hi = mid - 1` where appropriate.
Wrong move: An incomplete state merges distinct subproblems and caches incorrect answers.
Usually fails on: Correctness breaks on cases that differ only in hidden state.
Fix: Define state so each unique subproblem maps to one DP cell.