LeetCode 940 Dynamic Programming Solution After LeetCode 115

It's very interesting. LeetCode has given us a second Hard Dynamic problem for the Daily Challenge in a row. Yesterday, it was 115. Distinct Subsequences problem. I posted the solution here. Today it is 940. Distinct Subsequences II

Below are implementations of the Time O(n) and Space O(1) solution in several programming languages: C++, Java, JavaScript, TypeScript, Python.

LeetCode 940 C++ solution

class Solution {
public:
  int distinctSubseqII(string s) {
    const int MOD = 1e9 + 7;

    long long dp = 1;
    long long last[26] = {};

    for(char c : s)
    {
      int index = c - 'a';

      long long prevDp = dp;

      dp = (2 * dp - last[index] + MOD) % MOD;

      last[index] = prevDp;
    }

    return (dp - 1 + MOD) % MOD;
  }
};

LeetCode 940 Java solution

class Solution {
  public int distinctSubseqII(String s) {
    final long MOD = 1_000_000_007L;

    long dp = 1;
    long[] last = new long[26];

    for(char c : s.toCharArray()) {
      int idx = c - 'a';
      long prevDp = dp;

      dp = (2 * dp - last[idx] + MOD) % MOD;

      last[idx] = prevDp;
    }

    return (int) ((dp - 1 + MOD) % MOD);
  }
}

LeetCode 940 JavaScript solution

var distinctSubseqII = function(s) {
  const MOD = 1e9 + 7;

  let dp = 1;
  const last = new Array(26).fill(0);

  for(const c of s) {
    const idx = c.charCodeAt(0) - 97;
    const prevDp = dp;

    dp = (2 * dp - last[idx] + MOD) % MOD;

    last[idx] = prevDp;
  }

  return (dp - 1 + MOD) % MOD;
};

LeetCode 940 TypeScript solution

function distinctSubseqII(s: string): number {
  const MOD = 1e9 + 7;

  let dp = 1;
  const last: number[] = new Array(26).fill(0);

  for(const c of s) {
    const idx = c.charCodeAt(0) - 97;

    const prevDp = dp;

    dp = (2 * dp - last[idx] + MOD) % MOD;

    last[idx] = prevDp;
  }

  return (dp - 1 + MOD) % MOD;
};

LeetCode 940 Python solution

class Solution(object):
  def distinctSubseqII(self, s):
    MOD = 10**9 + 7

    dp = 1
    last = [0] * 26

    for c in s:
      idx = ord(c) - ord('a')

      prev_dp = dp

      dp = (2 * dp - last[idx] + MOD) % MOD

      last[idx] = prev_dp

  return (dp - 1 + MOD) % MOD