Learn All Patterns of Subsequences (Theory)
Subsequences Pattern DSA practice problem on Onlearn.
Difficulty: medium.
Topics: Learn All Patterns of Subsequences (Theory), Dynamic Programming, Recursion, String Manipulation, Hash Map, Time Complexity, Space Complexity, Modular Arithmetic, Subsequences, Arrays, bit manipulation, dynamic programming, backtracking, combinatorics, recursion, Subsequence Problems, Power Set (Bitmasking).
Count Distinct Subsequences Problem Statement Given a string s, your task is to find the number of distinct non empty subsequences of s. Since the number can be very large, return the result modulo 10^9 + 7. A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements. For example, "ace" is a subsequence of "abcde". Input Specification The input consists of a single line containing a string s. Output Specification Print a single integer, the count of distinct non empty subsequences of s, modulo 10^9 + 7. Constraints 1 <= |s| <= 10^5 s consists only of lowercase English letters ('a' through 'z'). Sample Test Cases Sample Input 1 Sample Output 1 Explanation 1 The distinct non empty subsequences of "abc" are: "a", "b", "c", "ab", "ac", "bc", "abc". Total 7. Sample Input 2 Sample Output 2 Explanation 2 The distinct non empty subsequences of "aba" are: "a", "b", "aa", "ab", "ba", "aba". Total 6.