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;
    // endsIn[i] := the number of subsequence that end in ('a' + i)
    vector<long> endsIn(26);

    for (const char c : s)
      endsIn[c - 'a'] = accumulate(endsIn.begin(), endsIn.end(), 1L) % kMod;

    return accumulate(endsIn.begin(), endsIn.end(), 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;
    // endsIn[i] := the number of subsequence that end in ('a' + i)
    long[] endsIn = new long[26];

    for (final char c : s.toCharArray())
      endsIn[c - 'a'] = (Arrays.stream(endsIn).sum() + 1) % kMod;

    return (int) (Arrays.stream(endsIn).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
    # endsIn[i] := the number of subsequence that end in ('a' + i)
    endsIn = [0] * 26

    for c in s:
      endsIn[string.ascii_lowercase.index(c)] = (sum(endsIn) + 1) % kMod

    return sum(endsIn) % kMod