What you need to understand before you start preparing for a Coding Interview

LeetCode 115: two solutions - Space optimization using a 1D array

A simple optimization using a 1D array gives us O(m) instead of O(n * m) Space complexity. The Time complexity remains O(n * m) in both cases.


The LeetCode 115. Distinct Subsequences problem.


LeetCode 115 C++ solution - O(n * m) Space

class Solution {
public:
    int numDistinct(string s, string t) {
      int n = s.size();
      int m = t.size();

      vector<vector<unsigned long long>> dp(n + 1, vector<unsigned long long>(m + 1));

      for(int i = 0; i <= n; i++) dp[i][0] = 1;

      for(int i = 1; i <= n; i++)
      {
        for(int j = 1; j <= m; j++)
        {
          dp[i][j] = dp[i - 1][j];

          if(s[i - 1] == t[j - 1]) dp[i][j] += dp[i - 1][j - 1];
        }
      }

      return dp[n][m];
    }
};

Instead of storing the entire DP table, we keep only one row.

The key point is that j must iterate from right to left because we need the old value from the previous state of s. If we iterated from left to right, we could use the already updated dp[j - 1] within the same iteration and count the same character from s multiple times.


LeetCode 115 solution - O(m) Space

class Solution {
public:
    int numDistinct(string s, string t) {
      int m = t.size();

      vector<unsigned long long> dp(m + 1, 0);
      dp[0] = 1;

      for(char c : s)
      {
        for(int j = m; j >= 1; j--)
          if(c == t[j - 1]) dp[j] += dp[j - 1];
      }

      return dp[m];
    }
};

Below are implementations of the O(m) solution in other programming languages.


LeetCode 115 Java solution

class Solution {
  public int numDistinct(String s, String t) {
    int m = t.length();

    long[] dp = new long[m + 1];
    dp[0] = 1;

    for(char c : s.toCharArray()) {
      for(int j = m; j >= 1; j--) {
        if(c == t.charAt(j - 1)) {dp[j] += dp[j - 1];
      }
    }

    return (int) dp[m];
  }
}

LeetCode 115 JavaScript solution

var numDistinct = function(s, t) {
  const m = t.length;

  const dp = new Array(m + 1).fill(0);
  dp[0] = 1;

  for(const c of s) {
    for(let j = m; j >= 1; j--) {
      if(c === t[j - 1]) dp[j] += dp[j - 1];
    }
  }

  return dp[m];
};

LeetCode 115 TypeScript solution

function numDistinct(s: string, t: string): number {
  const m = t.length;

  const dp: number[] = new Array(m + 1).fill(0);
  dp[0] = 1;

  for(const c of s) {
    for(let j = m; j >= 1; j--) {
      if(c === t[j - 1]) dp[j] += dp[j - 1];
    }
  }

  return dp[m];
};

LeetCode 115 Python solution

class Solution(object):
  def numDistinct(self, s, t):
    m = len(t)

    dp = [0] * (m + 1)
    dp[0] = 1

    for c in s:
      for j in range(m, 0, -1):
        if c == t[j - 1]:
          dp[j] += dp[j - 1]

    return dp[m]
© 2026 Algobytes