Skip to content

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<long> 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