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

Source: leetcode | Difficulty: MEDIUM
Tags: String algorithms

Dynamic programming

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:
		n = len(S)
		MOD = int(1000000000.0 + 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 = 1000000000 + 7
			l = 0
			for i in range(1, n + 1):
				l += len(set(combinations(S, i))) % MOD
			return l

		def from_soln():
			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
		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)
		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:
		(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)