Verifying Sequential Character Matches

Determining whether a string exists as a subsequence within another requires tracking character alignments while preserving relative ordering. This pattern establishes the foudnation for more advanced string alignment techniques like edit distance.

State Definition

Construct a two-dimensional table match_len[row][col] where row maps to the prefix of the pattern string (indices 0 through row-1) and col maps to the prefix of the text string (indices 0 through col-1). The value stored at each coordinate represents the maximum count of consecutive characters from the pattern successfully identified as a subsequence within the corresponding segment of the text.

Transition Logic

Evaluating characters at pattern[row-1] and text[col-1] yields two distinct paths:

• Characters Align: When pattern[row-1] == text[col-1], the current character extends a valid match. The accumulated count increases by one, inheriting results from both strings' previous prefixes: match_len[row][col] = match_len[row-1][col-1] + 1.
• Characters Diverge: When the characters differ, the current position in the text cannot contribute to matching the current pattern character. The solution falls back to results obtained by excluding this text character: match_len[row][col] = match_len[row][col-1].

Base Case Initialization

Allocate dimensions (pattern.length() + 1) x (text.length() + 1) initialized to zero. The zeroth row and column inherently represent comparisons against empty sequences, which naturally evaluate to zero matches. This padding eliminates boundary condition checks during iteration.

Traversal & Validation

Iterate row from 1 to pattern.length() and col from 1 to text.length(). Populate the matrix following the transition rules. Validation is achieved by comparing match_len[pattern.size()][text.size()] against pattern.size(). Equality confirms every pattern character was located sequentially.

bool isPatternPresent(const std::string& pattern, const std::string& text) {
    int pLen = pattern.size();
    int tLen = text.size();
    std::vector<std::vector<int>> match_len(pLen + 1, std::vector<int>(tLen + 1, 0));

    for (int i = 1; i <= pLen; ++i) {
        for (int j = 1; j <= tLen; ++j) {
            if (pattern[i - 1] == text[j - 1]) {
                match_len[i][j] = match_len[i - 1][j - 1] + 1;
            } else {
                match_len[i][j] = match_len[i][j - 1];
            }
        }
    }

    return match_len[pLen][tLen] == pLen;
}

Counting Distinct Subsequence Formations

Quantifying how many unique ways a target string can be extracted as a subsequence from a source string shifts focus from existence to combinatorial enumeration. Greedy two-pointer strategies fail here because multiple characters across the source can independently satisfy the same target positions, requiring state accumulation.

State Definition

Define ways[i][j] as the total number of distinct subsequences within source[0...i-1] that precisely reconstruct target[0...j-1]. Rows traverse the source material, columns traverse the target blueprint.

Transition Logic

Comparing source[i-1] and target[j-1] determines how combinations accumulate:

• Match Found: Identical characters permit two independent combination branches. We either utilize the current source character to satisfy the current target requirement (adding ways[i-1][j-1]), or we discard the current source character and rely entirely on preceding characters (adding ways[i-1][j]). Combined: ways[i][j] = ways[i-1][j-1] + ways[i-1][j].
• Mismatch Detected: Divergent characters mean source[i-1] cannot participate in forming target[j-1]. All valid configurations must originate from ignoring this source character: ways[i][j] = ways[i-1][j].

Base Case Initialization

Dimensions span (source.length() + 1) x (target.length() + 1).

• ways[i][0] = 1 for all i: An empty target string is universally extractable from any source prefix via complete deletion (exactly one configuration).
• ways[0][j] = 0 for j > 0: Non-empty targets cannot be constructed from an empty source.
• ways[0][0] = 1: Both sequences are empty, representing a single valid empty-to-empty mapping.

Traversal & Execution

Process rows sequentially from top to bottom, columns left to right. Each cell relies strictly on its immediate upper neighbor and upper-left diagonal neighbor, guaranteeing prerequisite values are computed beforehand. The terminal result resides at ways[source.size()][target.size()]. Internal calculations utilize extended integer types to prevent intermediate overflow before casting to the final output type.

int distinctSubsequenceCounts(const std::string& source, const std::string& target) {
    int sSize = source.size();
    int tSize = target.size();
    std::vector<std::vector<long long>> ways(sSize + 1, std::vector<long long>(tSize + 1, 0));

    for (int i = 0; i <= sSize; ++i) ways[i][0] = 1;
    // ways[0][j] remains 0 for j > 0 due to default initialization

    for (int i = 1; i <= sSize; ++i) {
        for (int j = 1; j <= tSize; ++j) {
            if (source[i - 1] == target[j - 1]) {
                ways[i][j] = ways[i - 1][j - 1] + ways[i - 1][j];
            } else {
                ways[i][j] = ways[i - 1][j];
            }
        }
    }

    return static_cast<int>(ways[sSize][tSize]);
}