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...
Microsoft Corporation Software Developer Intern interview questions & answers
A Software Developer Intern was asked 7mo agoQ. What were your responsibilities during your internship?
A Software Developer Intern was asked 7mo agoQ. What is the difference between polymorphism and inheritance?
A Software Developer Intern was asked 9mo agoQ. Given a string, reverse the order of characters using standard data structures a...read more
Popular interview questions of Software Developer Intern
A Software Developer Intern was asked 6mo agoQ1. What were your responsibilities during your internship?
A Software Developer Intern was asked 6mo agoQ2. What is the difference between polymorphism and inheritance?
A Software Developer Intern was asked 8mo agoQ3. Given a string, reverse the order of characters using standard data structures a...read more
>
Microsoft Corporation Software Developer Intern Interview 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

