Given a string S, count the number of distinct, non-empty subsequences of S .
Since the result may be large, return the answer modulo 10^9 + 7.
 
Example 1:
Input: "abc"
Output: 7
Explanation: The 7 distinct subsequences are "a", "b", "c", "ab", "ac", "bc", and "abc".


Example 2:
Input: "aba"
Output: 6
Explanation: The 6 distinct subsequences are "a", "b", "ab", "ba", "aa" and "aba".


Example 3:
Input: "aaa"
Output: 3
Explanation: The 3 distinct subsequences are "a", "aa" and "aaa".



 
 
Note:

S contains only lowercase letters.
1 <= S.length <= 2000

Difficulty: interview

Starter code:

class Solution:
    def distinctSubseqII(self, S: str) -> int:
        

Solutions:
class Solution:
    def distinctSubseqII(self, s: str) -> int:
        n = len(s)
        MOD = 10**9 + 7
        seen = dict()
        
        a = 1
        for i in range(n):
            char = s[i]
            b = 2 * a
            if char in seen:
                b -= seen[char]
            
            b %= MOD
            seen[char] = a
            a = b
        return a - 1
                


class Solution:
    def distinctSubseqII(self, S: str) -> int:
        
        # DP(i) = number of distinct subseq ending at i
        # DP(i) = 1 + sum(DP[:i]) if it is a new letter
        # DP(i) = 1 + sum(DP[j:i]) where j is last occurence of letter S[i]
        
        # abc -> [1, 2, 4]
        # aba -> [1, 2, 3]
        # aaa -> [1, 1, 1]
        # abaa -> [1, 2, 3, 3] a, b, ab, aa, ba, aba, aaa, baa, abaaa
        
        n = len(S)
        MOD = int(1e9 + 7)
        I = dict()
        PS = [0] * (n + 1)
        
        for i, c in enumerate(S):
            if c not in I:
                dpi = 1 + PS[i] % MOD
            else:
                dpi = PS[i] - PS[I[c]]
            I[c] = i
            PS[i + 1] = PS[i] + dpi
            
        return PS[-1] % MOD
    


class Solution:
    def distinctSubseqII(self, S: str) -> int:
        res, last = 1, {}
        for c in S:
            temp = res * 2
            if c in last:
                temp -= last[c]
            last[c] = res
            res = temp
        return (res - 1) % (10**9 + 7)


class Solution:
    def distinctSubseqII(self, S: str) -> int:
        def itertools_appr():
            if not S: return 0
            from itertools import combinations
            n = len(S)
            MOD = 1000_000_000 + 7
            l = 0
            for i in range(1,n+1):
                l += len(set(combinations(S, i))) % MOD
            return l
        
        def from_soln():
            '''
            Imagine we knew the subsequence count without the last char, dp[-1]
            dp[-1] should be twice of the previous one. However we need to account
            for the presence of the same last char previously.
            S = \"abab\"
            dp[0], with chars upto S[0] = { '', 'a' }
            dp[1], with chars upto S[1] = dp[1] * 2 - subseqs we would have
                double counted. {'', 'a', 'b', 'ab'}
                = 4
            dp[2], with chars upto S[2] = 2*dp[1] - adj for double counting
                {'', 'a', 'b', 'ab'} --> dp[1]
                {'a', 'aa', 'ba', 'aba'} --> dp[1] + 'a'
                'a' is double counted = dp[last['a']] - 1
                = 7
            dp[3], with chars upto S[3] = 2*dp[2] - adjustments for double counting
                {'','a','b','ab','aa','ba','aba'} <-- dp[2]
                {'b','ab','bb','abb','aab','bab','abab'} <-- dp[2] + 'b'
                'b', 'ab' are double counted = dp[last['b']] - 1
                = 14
            
            dp[k] = 2*dp[k-1] - dp[last[S[k]]] - 1, (1 for '')
            '''
            dp = [1]
            last = {}
            for i,x in enumerate(S):
                dp.append(2*dp[-1])
                if x in last:
                    dp[-1] -= dp[last[x]]
                last[x] = i
            return (dp[-1] - 1) % (10**9+7)
        return from_soln()


from collections import Counter
class Solution:
    def distinctSubseqII(self, S: str) -> int:
        res = 1
        endCount = Counter()
        for s in S:
            res, endCount[s] = 2 * res - endCount[s], res
        return (res-1) % (10 ** 9 + 7)


class Solution:
    def distinctSubseqII(self, s: str) -> int:        
        dp = Counter()
        for c in s: dp[c] = sum(dp.values()) + 1
        return sum(dp.values()) % (10**9+7)

class Solution(object):
    def distinctSubseqII(self, S):
        dp = [1]
        last = {}
        for i, x in enumerate(S):
            dp.append(dp[-1] * 2)
            if x in last:
                dp[-1] -= dp[last[x]]
            last[x] = i

        return (dp[-1] - 1) % (10**9 + 7)

class Solution:
    def distinctSubseqII(self, S: str) -> int:
        mod=1000000007
        if(not S):
            return 0
        d={}
        dp=[0 for i in range(0,len(S))]
        dp[0]=2
        d[S[0]] = 0
        for i in range(1,len(S)):
            dp[i] = 2*dp[i-1]
            v=0
            if(S[i] in d):
                last=d[S[i]]
                if(last-1>=0):
                    v=dp[last-1]
                else:
                    v=1
            dp[i] = (dp[i] - v)%mod
            d[S[i]] = i
        return dp[-1]-1

class Solution:
    def distinctSubseqII(self, S: str) -> int:
        mod = 10**9 + 7
        n = len(S)
        dp = [0] * n
        dp[0] = 1
        for i in range(1, n):
            dp[i] = dp[i - 1] * 2 + 1
            for j in range(i - 1, -1, -1):
                if S[j] == S[i]:
                    if j > 0:
                        dp[i] -= dp[j - 1]
                    dp[i] -= 1
                    break
            dp[i] %= mod
        # print(dp)
        return dp[-1]

class Solution:
    def distinctSubseqII(self, S: str) -> int:
        MOD = 10**9 + 7
        memo = {}
        def dp(i, j):
            if i > j: return 0
            if(i, j) not in memo:
                ans = 1 + dp(i+1, j) * 2
                for k in range(i+1, j+1):
                    if S[k] == S[i]:
                        ans = dp(i+1, j) * 2 - dp(k+1, j)
                        break
                memo[i, j] = ans
            return memo[i, j]
        return dp(0, len(S) - 1) % MOD


class Solution:
    def distinctSubseqII(self, S: str) -> int:
        cache = {}
        extras = []
        
        module = 10 ** 9 + 7
        _sum = 0
        for i, s in enumerate(S):
            if i == 0:
                _sum += 1
                extras.append(1)
            else:
                prev_indexes = cache.setdefault(s, [])
                if not prev_indexes:
                    extras.append(_sum + 1)
                    _sum += (_sum + 1)
                else:
                    duplicated = sum([extras[j] for j in prev_indexes])
                    extras.append(_sum + 1 - duplicated)
                    
                    _sum += _sum + 1 - duplicated
            cache.setdefault(s, []).append(i)
        return _sum % (module)

class Solution:
    def distinctSubseqII(self, S: str) -> int:
        ln = 1000000007
        if len(S) == 0:
            return 0
        l = [1]
        
        for i in range(1, len(S)):
            cur = 0
            for j in range(i-1, -1, -1):
                cur += l[j]
                if S[i] == S[j]:
                    break
                if j == 0:
                    cur +=1
                    
            l.append(cur%ln)
        
        #print(l)
        res = 0
        for i in l:
            res += i
            res %=ln
        
        return res

class Solution:
    def distinctSubseqII(self, S: str) -> int:
        MOD = 10**9 + 7
        
        cur = collections.defaultdict(int)
        for c in S:
            for k in [k for k in cur.keys()]:
                if c!=k:
                    cur[c] += cur[k]
            cur[c] += 1
            cur[c] %= MOD
        
        
        return sum(cur.values()) % MOD

class Solution:
    def distinctSubseqII(self, S: str) -> int:
        K = 1000000000 + 7
        n = len(S)
        dp = [0 for i in range(n+1)]
        dp[0] = 1
        umap = dict()
        
        for i in range(n):
            dp[i+1] = (2 * dp[i]) % K
            if S[i] in umap:
                dp[i+1] -= dp[umap[S[i]]]
            dp[i+1] %= K
            umap[S[i]] = i
        
        result = dp[n] - 1
        if result < 0:
            result += K
        return result

class Solution:
    def distinctSubseqII(self, S: str) -> int:
        
        # DP(i) = number of distinct subseq ending at i
        
        # DP(i) = 1 + sum(DP[:i]) if it is a new letter
        
        # DP(i) = 1 + sum(DP[j:i]) where j is last occurence of letter S[i]
        
        # abc -> [1, 2, 4]
        # aba -> [1, 2, 3]
        # aaa -> [1, 1, 1]
        # abaa -> [1, 2, 3, 3] a, b, ab, aa, ba, aba, aaa, baa, abaaa
        
        n = len(S)
        MOD = int(1e9 + 7)
        DP = [0] * n
        I = dict()
        
        for i, c in enumerate(S):
            if c not in I:
                DP[i] = 1 + sum(DP[:i]) % MOD
            else:
                DP[i] = sum(DP[I[c]:]) % MOD
            I[c] = i
            
        return sum(DP) % MOD
    


class Solution:
    def distinctSubseqII(self, S: str) -> int:
        res, endwith = 0, collections.Counter()
        for c in S:
            res, endwith[c] = res * 2 + 1 - endwith[c], res + 1
        
        return res % (7+10**9)
        


class Solution:
    def distinctSubseqII(self, S: str) -> int:
        MOD = 10 ** 9 + 7
        n = len(S)
        dp = collections.Counter()
        result = 0
        for i in range(n - 1, -1, -1):
            old = result
            result = (2 * old + 1 - dp[S[i]]) % MOD
            dp[S[i]] += result - old
        return result

class Solution:
    def distinctSubseqII(self, s: str) -> int:
        isvisited =[-1]*len(s)
        d=dict()
        for i in range(len(s)):
            if s[i] in d:
                isvisited[i] = d[s[i]] 
            d[s[i]] =i 
        dp = [1]*(len(s)+1)
        for i in range(1,len(s)+1):
            if isvisited[i-1] == -1:
                dp[i]=dp[i-1]*2
            else:
                dp[i] = 2*dp[i-1]- dp[isvisited[i-1]]
        return (dp[-1]-1)%1000000007

class Solution:
    def distinctSubseqII(self, S: str) -> int:
        dp, mod = [0] * len(S), 10**9 + 7
        for i, char in enumerate(S):
            ind = S.rfind(char, 0, i)
            dp[i] = 1 + sum(dp[:i]) % mod if ind == -1 else sum(dp[ind:i]) % mod
        return sum(dp) % mod


class Solution(object):
    def distinctSubseqII(self, S):
        prev = collections.defaultdict(int)
        res = 1
        for c in S:
            new = res - prev[c]
            res += new
            prev[c] += new
        return (res - 1) % (10**9 + 7)  

class Solution:
    def distinctSubseqII(self, S: str) -> int:
        # Dynamic Programming
        # Time  complexity: O(N)
        # Space complexity: O(N)
        # dp, last = [1], {}
        # for i, x in enumerate(S):
        #     dp.append(dp[-1] * 2)
        #     if x in last:
        #         dp[-1] -= dp[last[x]]
        #     last[x] = i

        # return (dp[-1] - 1) % (10**9 + 7)


        dp, MOD = [0] * len(S), 10**9 + 7
        for i, char in enumerate(S):
            ind = S.rfind(char, 0, i)
            dp[i] = 1 + sum(dp[:i]) % MOD if ind == -1 else sum(dp[ind:i]) % MOD
        return sum(dp) % MOD