Problem 115

Abstract / Summary

Given two strings s and t count how many different ways t can appear as a subsequence of s without repeating any sequence.

Note

The full problem description, including helpful examples, can be found on LeetCode.

Python 0115.py

class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        @cache
        def deeper(posS, posT):
            if posT == len(t):
                return 1 # match
            if posS == len(s):
                return 0 # incomplete

            if s[posS] == t[posT]:
                return deeper(posS + 1, posT + 1) + deeper(posS + 1, posT) # consume letter or skip letter
            else:
                return                              deeper(posS + 1, posT) # need to skip letter

        result = deeper(0, 0)
        if result >= 2**31: # ??? weird test case, requires -1 if result is too large
            result = -1
        return result
18 lines | 685 bytes | submitted August 30, 2023 | GitHub   31% comment ratio | tab size 4 | low complexity

Difficulty

This problem is ranked as
easy medium hard

and has an acceptance rate of about 52% (1+ million submissions).

Typical patterns to solve this problem:
  • Dynamic Programming
  • String
I solved 663 easy, 1250 medium and 309 hard problems

AI Disclaimer

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.
LeetCode profile | GitHub repo

Code Walkthrough

Overview

The provided implementation solves the classic “distinct subsequences” problem: given two strings s and t, it counts how many ways t can be formed by deleting characters from s while preserving order. The solution is expressed as a depth-first recursion with memoization, which systematically explores the decision at each character of s to either match it with the current character of t or skip it. A final guard converts results that exceed a 32-bit signed integer limit into -1.

Recursive Structure

The core of the algorithm is the nested function deeper(posS, posT). It receives two indices: posS points to the current character in s, and posT points to the current character in t. The function returns the number of distinct ways the suffix t[posT:] can be matched using the suffix s[posS:].

@cache
def deeper(posS, posT):
    ...

The @cache decorator automatically stores previously computed results, turning the exponential recursion into a polynomial-time dynamic programming solution.

Base Cases

Two termination conditions are checked first:

  1. When posT reaches the length of t, the entire target string has been matched. The function returns 1, representing a single successful construction.
  2. When posS reaches the length of s while posT has not, there are no remaining characters to consume, so the function returns 0.
if posT == len(t):
    return 1          # full match achieved
if posS == len(s):
    return 0          # source exhausted without completing match

These base cases correctly handle the situation where the target is empty (always one match) and where the source is exhausted prematurely.

Transition Logic

When both indices are within bounds, the algorithm decides based on character equality:

  • If s[posS] equals t[posT], two recursive branches are taken:
    • Advance both indices, consuming the matching character.
    • Advance only posS, skipping the character in s while keeping the target position unchanged. The sum of these branches yields the total count for the current state.
if s[posS] == t[posT]:
    return deeper(posS + 1, posT + 1) + deeper(posS + 1, posT)
  • If the characters differ, the only viable action is to skip the current character of s and continue searching.
else:
    return deeper(posS + 1, posT)

This dichotomy ensures that every possible subsequence alignment is explored exactly once.

Result Post-Processing

After the recursive exploration finishes, the top-level call deeper(0, 0) yields the total number of distinct subsequences. The code then checks whether this total exceeds the 32-bit signed integer range (2**31). If it does, the specification demands returning -1 instead of the raw count.

result = deeper(0, 0)
if result >= 2**31:
    result = -1
return result

This guard handles extreme inputs where the combinatorial explosion would otherwise produce a value that cannot be represented in a 32-bit signed integer.

Memoization and Caching

The use of @cache (available from Python 3.9 onward) is the primary performance optimization. By caching the result of each (posS, posT) pair, the algorithm avoids recomputing identical subproblems. The recursion tree collapses into a directed acyclic graph whose nodes correspond to unique index pairs. Consequently, each state is evaluated once, and the total number of states is bounded by len(s) * len(t). The cache also implicitly provides fast lookup for previously solved sub-instances, turning the naive exponential recursion into a dynamic programming solution with deterministic execution time.

Edge Cases Handled

The implementation gracefully handles several edge conditions:

  • Empty target string: When t is empty, the base case posT == len(t) triggers immediately, returning 1. This reflects the mathematical fact that there is exactly one way to form an empty subsequence (by deleting all characters).
  • Empty source string with non-empty target: The second base case returns 0, indicating that a non-empty target cannot be formed from an empty source.
  • Identical source and target: The recursion will match each character and progress both indices together, ultimately reaching the full-match base case, yielding a count of 1.
  • Source shorter than target: The recursion will exhaust s before t can be fully matched, causing the second base case to fire and propagate 0 up the call stack.
  • Large combinatorial counts: The final guard for values >= 2**31 ensures that the function complies with the requirement to return -1 for overflow scenarios, preventing unintended large integer returns.

Performance Optimizations

Beyond memoization, the code benefits from the following implicit optimizations:

  • Tail-call avoidance: By returning the sum of two recursive calls only when characters match, the algorithm minimizes unnecessary recursion depth for mismatched characters, directly proceeding to the next source index.
  • Early termination: The base case for a fully matched target (posT == len(t)) stops further recursion as soon as a valid subsequence is found, preventing wasteful exploration of remaining source characters.
  • Cache locality: Since the cache keys are simple integer tuples, Python’s built-in dictionary implementation provides fast hashing and retrieval, contributing to low overhead per memoized lookup.

Overall, the combination of a clear recursive formulation, exhaustive base case handling, and built-in memoization yields an implementation that is both conceptually straightforward and computationally efficient for the problem domain.

written by openai gpt

ELI5 - Simplified Explanation

Imagine there is a big pile of letter blocks laid out in a long row called s. There is also a smaller list of blocks called t that spells out a secret word. The goal is to figure out how many different ways those secret blocks can be picked out from the long row while keeping them in the exact same order.

The code works by looking at the blocks one by one. It starts by looking at the very first letter of the row and the first letter of the secret word. If the letters match, there is an exciting choice. It can use that letter to help spell the secret word, or it can leave that letter behind and keep looking for a match further down the row. If the letters do not match, it has to move on to the next block in the long row to keep hunting for the right one.

This process keeps repeating, always exploring both possibilities whenever a match is found. Because this could take a very long time, the code remembers the answers it has already figured out to save time later. Think of it like a map that keeps track of where it has already been. Finally, the code adds up all the different successful ways it found to spell the secret word. If the number of ways is truly massive, it just keeps track of that special case.

written by google gemini

Code Quality

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):
n = 27 | median = 7 | μ = 6.63 | σ = 1.42

Complexity Analysis

Time: polynomial
As a rule of thumb, the maximum input size for one second execution time is
  • factorial: up to 10 elements
  • exponential: up to 20 elements
  • polynomial: a few thousand elements
  • loglinear: up to 100,000 elements
  • linear: a few million elements
  • logarithmic: a billion elements
  • constant: practically unlimited
generated automatically

Other Solutions

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)
author
author solutions
www AlgoMonster C++ Python Java TS
WalkCCC C++ Python Java
leetcode.ca C++ Python Rust Java Go TS
LeetcodeHelp C++ Python Java
MemoryLimitExceeded C++ Python
Progiez C++ Python Java
github aylei Rust
begeekmyfriend C
BigEggStudy C#
black-shadows Python
charles-wangkai Java
chenyanzhe C++
everthis JS
fartem Ruby
fpdjsns C++
gaosq0604 Python
Garvit244 Python
gouthampradhan Java
halfrost Go
haoel C++
JoshCrozier JS
keineahnung2345 C++
lennylxx C
linouk23 C++
lkwq007 Python
luangong C++
MacJim C++
qiyuangong Python
ruoru Rust
suxrobGM C#
trung-hn Python
wisdompeak C++
zfang399 C++
AlgoMonster C++, Python, Java, TypeScript
WalkCCC C++, Python, Java
leetcode.ca C++, Go, Java, Python, Rust, TypeScript
LeetcodeHelp C++, Java, Python
MemoryLimitExceeded Python, C++
Progiez C++, Java, Python
aylei Rust
begeekmyfriend C
BigEggStudy C#
black-shadows Python, Python
charles-wangkai Java
chenyanzhe C++
everthis JavaScript
fartem Ruby
fpdjsns C++
gaosq0604 Python
Garvit244 Python
gouthampradhan Java
halfrost Go
haoel C++
JoshCrozier JavaScript
keineahnung2345 C++
lennylxx C
linouk23 C++
lkwq007 Python
luangong C++
MacJim C++
qiyuangong Python
ruoru Rust
suxrobGM C#
trung-hn Python
wisdompeak C++
zfang399 C++
48 links | 33 authors | 10 languages

Videos

15 videos   did my crawler come up with invalid videos ? drop me a line.

Solved On The Same Day

1 easy 3 medium 1 hard
6 solutions   August 30, 2023

Extra

There are a few extra pages giving you some insights into my setup:
  • Tech Stack - my development environment and tools
  • AI - how AI helped me create this website (NOT solving the problems)
  • Progress - progression over time
  • Quality - code quality