# 940. Distinct Subsequences II

• Time: $O(26n) = O(n)$
• Space: $O(26) = O(1)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 class Solution { public: int distinctSubseqII(string s) { constexpr int kMod = 1'000'000'007; // endsWith[i] := # of subseqs ends with 'a' + i vector endsWith(26); for (const char c : s) endsWith[c - 'a'] = accumulate(begin(endsWith), end(endsWith), 1L) % kMod; return accumulate(begin(endsWith), end(endsWith), 0L) % kMod; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 class Solution { public int distinctSubseqII(String s) { final int kMod = 1_000_000_007; // endsWith[i] := # of subseqs ends with 'a' + i long[] endsWith = new long[26]; for (final char c : s.toCharArray()) endsWith[c - 'a'] = (Arrays.stream(endsWith).sum() + 1) % kMod; return (int) (Arrays.stream(endsWith).sum() % kMod); } } 
  1 2 3 4 5 6 7 8 9 10 class Solution: def distinctSubseqII(self, s: str) -> int: kMod = 1_000_000_007 # endsWith[i] := # of subseqs ends with 'a' + i endsWith = [0] * 26 for c in s: endsWith[ord(c) - ord('a')] = (sum(endsWith) + 1) % kMod return sum(endsWith) % kMod