Diwali Offer!Flat 20% OFF
Enroll Now
PrakalpanaLive online tech training

181. Distinct Subsequences

HardDay 53 of 60Dynamic Programming

Given two strings s and t, count how many different subsequences of s are equal to t. Two subsequences are different if they use a different set of positions in s. The final answer fits in a 32-bit signed integer.

Example 1
Input: s = "rabbbit", t = "rabbit"
Output: 3
Any two of the three b characters can be used, giving 3 ways.
Example 2
Input: s = "babgbag", t = "bag"
Output: 5
Constraints
  • 1 <= s.length, t.length <= 1000
  • `s` and `t` have English letters
  • The answer fits in a 32-bit signed integer
Hints
Frequently asked at: Google, Amazon, Microsoft
Ctrl + Enter runs the examples

Not sure what to learn next?

A 1-on-1 session with an industry mentor and a roadmap built for you. How it works

  1. 1Discuss your goals
  2. 2Get a personal plan
  3. 3Start learning
Book for β‚Ή200/ 30 min