PPractick

The problem

You're building a plagiarism-detection / template-matching feature for a document-review tool. Given a source document string s and a target pattern string t, you need to count how many distinct ways t can be formed by deleting some characters from s (without reordering the remaining ones). This tells the compliance team how many independent "occurrences" of a suspicious phrase pattern exist within a larger blob of text, even when the phrase is interleaved with other content.

Formally: given strings s and t, return the number of distinct subsequences of s which equal t.

Function signature

int numDistinct(string s, string t);

Test cases

s	t	Output	Explanation
"rabbbit"	"rabbit"	3	3 ways: choosing different b's at position 3,4, or 5 to skip
"babgbag"	"bag"	5	5 distinct index-subsequences spell "bag"
"abc"	"abc"	1	only one way — pick every character
"abc"	""	1	empty string is a subsequence of everything, exactly once (delete everything)
""	"abc"	0	can't form a non-empty target from an empty source
"aaa"	"a"	3	pick any one of the 3 a's
"abc"	"abcd"	0	t longer than s, impossible

(Note: counts can get large — this maps naturally to unsigned long long or int per LeetCode constraints, but mention overflow awareness.)

How interviewers phrase it

• "Given a big string and a pattern, how many ways can you delete characters from the big string to get exactly the pattern?"
• "Count the number of times t appears as a subsequence (not substring) of s."
• Sometimes disguised as: "How many distinct ways can you form the word 'bag' by deleting letters from 'babgbag'?"

Clarifying questions to ask

1. Is this subsequence (order preserved, but not contiguous) or substring (contiguous)? — critical distinction, confirm explicitly.
2. Are s and t guaranteed non-empty, or do I need to handle empty-string edge cases?
3. Should counting be case-sensitive?
4. Can the answer overflow a 32-bit int for large inputs? What's the expected length of s and t?
5. Do distinct subsequences mean distinct index selections (even if characters look identical), or distinct resulting strings? — Standard problem means distinct index selections (this is why "aaa"/"a" gives 3, not 1).

Follow-ups to expect

1. "Can you optimize space?"
2. "Can you solve it recursively with memoization first?"
3. "What if you needed to actually list out the subsequences, not just count them?"
4. "How does this relate to Longest Common Subsequence (LCS)?"
5. "What if t could contain wildcard characters (like . matching any character)?"
6. "Can you do it with rolling array / bitset tricks for very large inputs?"

Related questions

• Longest common subsequence Hard
• Print Longest Common Subsequence Hard
• Longest common substring Hard
• Longest palindromic subsequence Hard
• Minimum insertions to make string palindrome Hard
• Minimum insertions or deletions to convert string A to B Hard

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in