Distinct Subsequences of a String
Given a string S
of length N
that may contain duplicate alphabets, your task is to compute the count of distinct subsequences of this string.
Example:
Input:
S = "deed"
Output:
11
Explanation:
The possible subsequences include: {""}, {"d"}, {"e"}, {"de"}, {"ee"}, {"dee"}, {"dd"}, {"ed"}, {"ded"}, {"eed"}, {"deed"}. Removing duplicates gives us 11 distinct subsequences.
Constraints:
1 <= T <= 10
1 <= N <= 10^4
Note: The answer can be large, so return it modulo 10^9 + 7
.
Input:
T (number of test cases)
string S (for each test case)
Output:
The count of distinct subsequences for each test case, displayed on separate lines.
Note: You do not need to print anything explicitly. Just implement the function to return the result.

AnswerBot
4mo
Compute the count of distinct subsequences of a string with possible duplicates.
Use dynamic programming to keep track of distinct subsequences.
Consider the cases where the current character is include...read more
Help your peers!
Add answer anonymously...
Top Software Developer Intern Interview Questions Asked at Microsoft Corporation
Q. What is the difference between polymorphism and inheritance?
Q. What were your responsibilities during your internship?
Q. Given a string, reverse the order of characters using standard data structures a...read more
Interview Questions Asked to Software Developer Intern at Other Companies
Top Skill-Based Questions for Microsoft Corporation Software Developer Intern
Algorithms Interview Questions and Answers
250 Questions
Data Structures Interview Questions and Answers
250 Questions
Web Development Interview Questions and Answers
250 Questions
Operating Systems Interview Questions and Answers
250 Questions
System Design Interview Questions and Answers
250 Questions
C++ Interview Questions and Answers
150 Questions
Stay ahead in your career. Get AmbitionBox app


Trusted by over 1.5 Crore job seekers to find their right fit company
80 L+
Reviews
10L+
Interviews
4 Cr+
Salaries
1.5 Cr+
Users
Contribute to help millions
AmbitionBox Awards
Get AmbitionBox app

