字串 DP（雙序列網格模式）

// java
// IDEA: the shared skeleton of every two-sequence grid DP
// time = O(m * n), space = O(m * n)
public int stringDP(String s1, String s2) {
    int m = s1.length(), n = s2.length();
    int[][] dp = new int[m + 1][n + 1];

    // Step 1: Initialize base cases (empty string states)
    dp[0][0] = 0; // Both strings empty

    // Initialize first row (s1 is empty)
    for (int j = 1; j <= n; j++) {
        dp[0][j] = initValueForEmptyS1(j);
    }

    // Initialize first column (s2 is empty)
    for (int i = 1; i <= m; i++) {
        dp[i][0] = initValueForEmptyS2(i);
    }

    // Step 2: Fill the DP table
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            // NOTE: Use i-1 and j-1 to access string characters
            if (s1.charAt(i-1) == s2.charAt(j-1)) {
                // Characters match
                dp[i][j] = transitionOnMatch(dp, i, j);
            } else {
                // Characters don't match
                dp[i][j] = transitionOnMismatch(dp, i, j);
            }
        }
    }

    return dp[m][n];
}

// java
// LC 1143 - Longest Common Subsequence
// IDEA: diagonal + 1 on a match, else the better of dropping one character
// time = O(m * n), space = O(m * n)
public int longestCommonSubsequence(String s1, String s2) {
    int m = s1.length(), n = s2.length();
    int[] prev = new int[n + 1];

    for (int i = 1; i <= m; i++) {
        int[] curr = new int[n + 1];
        for (int j = 1; j <= n; j++) {
            if (s1.charAt(i-1) == s2.charAt(j-1)) {
                curr[j] = prev[j-1] + 1; // Diagonal
            } else {
                curr[j] = Math.max(prev[j], curr[j-1]); // Top or left
            }
        }
        prev = curr; // Roll forward
    }

    return prev[n];
}

✅ CORRECT: 1-indexed approach
   dp[i][j] = answer for string1.substring(0, i) and string2.substring(0, j)
   - Row index i ∈ [0, m] where m = string1.length()
   - Col index j ∈ [0, n] where n = string2.length()
   - Character comparison: string1.charAt(i-1) vs string2.charAt(j-1)

❌ WRONG: 0-indexed approach (will cause boundary issues)
   - No room for "empty string" base case
   - First iteration accesses negative indices

Example: string1 = "abcde", string2 = "ace"

When i=3, j=2 (processing prefixes "abc" and "ac"):
  - DP state represents: LCS("abc", "ac")
  - We compare: string1.charAt(3-1) = 'c' with string2.charAt(2-1) = 'c'
  - The characters at POSITION (i-1) and (j-1) are what define the LAST character of each prefix

Index Mapping:
  i=0: prefix length 0 (empty string)
  i=1: prefix length 1 (first 1 char) → access string1[0]
  i=2: prefix length 2 (first 2 chars) → access string1[1]
  i=3: prefix length 3 (first 3 chars) → access string1[2]
  ...
  Therefore: when at dp[i][j], compare string1[i-1] with string2[j-1]

// java
// IDEA: the match / mismatch branch, isolated
// Pattern: Two cases only
if (string1.charAt(i - 1) == string2.charAt(j - 1)) {
    // CASE 1: Characters match → extend previous best result
    // The matching characters contribute +1 to the LCS length
    dp[i][j] = 1 + dp[i - 1][j - 1];  // Diagonal: both strings move forward
} else {
    // CASE 2: Characters don't match → take best of skipping either string
    // We have two choices:
    //   Option A: Skip current char from string1 → dp[i-1][j]
    //   Option B: Skip current char from string2 → dp[i][j-1]
    // Take whichever gives the better result
    dp[i][j] = Math.max(dp[i - 1][j],    // Skip from string1
                       dp[i][j - 1]);    // Skip from string2
}

string1 = "abcde"
string2 = "ace"

DP Grid (showing values):
        ""  a   c   e
    ""  0   0   0   0
    a   0   1   1   1
    b   0   1   1   1
    c   0   1   2   2
    d   0   1   2   2
    e   0   1   2   3

How to read:
  dp[4][2] = 2 means LCS("abcd", "ac") has length 2
  dp[5][3] = 3 means LCS("abcde", "ace") has length 3 ✓

Key moments:
  - dp[1][1]: Compare 'a' with 'a' → match! → dp[0][0] + 1 = 1
  - dp[2][1]: Compare 'b' with 'a' → no match → max(dp[1][1], dp[2][0]) = 1
  - dp[3][2]: Compare 'c' with 'c' → match! → dp[2][1] + 1 = 2
  - dp[5][3]: Compare 'e' with 'e' → match! → dp[4][2] + 1 = 3

// java
// LC 1143 - Longest Common Subsequence
// IDEA: same recurrence, written as the canonical 1-indexed table
// time = O(m * n), space = O(m * n)
public int longestCommonSubsequence(String text1, String text2) {
    int m = text1.length();
    int n = text2.length();

    // Create (m+1) × (n+1) table to handle "empty string" base case
    int[][] dp = new int[m + 1][n + 1];
    // dp[0][j] and dp[i][0] are already 0 (empty string has LCS of 0)

    // Loop uses 1-based indices to represent prefix lengths
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            // i represents prefix length in text1
            // j represents prefix length in text2
            // Compare character at position i-1 and j-1 (0-indexed)
            if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                // Characters match: extend the best previous result
                dp[i][j] = 1 + dp[i - 1][j - 1];
            } else {
                // Characters don't match: choose best by skipping either string
                dp[i][j] = Math.max(dp[i - 1][j],    // Skip from text1
                                   dp[i][j - 1]);    // Skip from text2
            }
        }
    }

    return dp[m][n];  // Answer for full strings
}

dp[i][j] = (dp[i-1][j] && s1[i-1] == s3[i+j-1])   // take from s1
         || (dp[i][j-1] && s2[j-1] == s3[i+j-1])   // take from s2

// java
// LC 678 - Valid Parenthesis String
// IDEA: greedy — carry the min/max possible open count instead of a DP table
// time = O(n), space = O(1)
public boolean checkValidString(String s) {
    int minParenCnt = 0; // minimum possible unmatched '('
    int maxParenCnt = 0; // maximum possible unmatched '('

    for (char c : s.toCharArray()) {
        if (c == '(') {
            minParenCnt++;
            maxParenCnt++;
        } else if (c == ')') {
            minParenCnt--;
            maxParenCnt--;
        } else { // '*' - wildcard
            minParenCnt--; // treat '*' as ')'
            maxParenCnt++; // treat '*' as '('
        }

        // If maxParenCnt < 0: too many unmatched ')'
        if (maxParenCnt < 0) return false;

        // If minParenCnt < 0: reset to 0 (can use '*' as empty)
        if (minParenCnt < 0) minParenCnt = 0;
    }

    // Valid if we can have 0 unmatched '('
    return minParenCnt == 0;
}

// java
// LC 678 - Valid Parenthesis String
// IDEA: dp[i][open] = can s[i:] close with `open` brackets already outstanding
// time = O(n^2), space = O(n^2)
public boolean checkValidString(String s) {
    int n = s.length();
    boolean[][] dp = new boolean[n + 1][n + 1];
    dp[0][0] = true; // empty string, 0 open parens

    for (int i = 1; i <= n; i++) {
        char c = s.charAt(i - 1);
        for (int j = 0; j <= n; j++) {
            if (c == '(') {
                // Add one open paren
                if (j > 0) dp[i][j] = dp[i - 1][j - 1];
            } else if (c == ')') {
                // Close one open paren
                if (j < n) dp[i][j] = dp[i - 1][j + 1];
            } else { // '*'
                // Option 1: treat '*' as empty
                dp[i][j] = dp[i - 1][j];
                // Option 2: treat '*' as '('
                if (j > 0) dp[i][j] |= dp[i - 1][j - 1];
                // Option 3: treat '*' as ')'
                if (j < n) dp[i][j] |= dp[i - 1][j + 1];
            }
        }
    }

    return dp[n][0]; // n chars processed, 0 open parens
}

// java
// LC 678 - Valid Parenthesis String
// IDEA: interval DP — dp[i][j] = is s[i..j] a valid string on its own
// time = O(n^3), space = O(n^2)
public boolean checkValidString(String s) {
    int n = s.length();
    if (n == 0) return true;

    boolean[][] dp = new boolean[n][n];

    // Base case: single character valid only if '*'
    for (int i = 0; i < n; i++) {
        if (s.charAt(i) == '*') dp[i][i] = true;
    }

    // Fill table for increasing lengths
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i <= n - len; i++) {
            int j = i + len - 1;

            // Option A: s[i] and s[j] form a matching pair
            if ((s.charAt(i) == '(' || s.charAt(i) == '*') &&
                (s.charAt(j) == ')' || s.charAt(j) == '*')) {
                if (len == 2 || dp[i + 1][j - 1]) {
                    dp[i][j] = true;
                }
            }

            // Option B: Split at some point k
            if (!dp[i][j]) {
                for (int k = i; k < j; k++) {
                    if (dp[i][k] && dp[k + 1][j]) {
                        dp[i][j] = true;
                        break;
                    }
                }
            }
        }
    }

    return dp[0][n - 1];
}

// java
// LC 678 - Valid Parenthesis String
// IDEA: top-down recursion on (index, open) with memoisation
// time = O(n^2), space = O(n^2)
public boolean checkValidString(String s) {
    int n = s.length();
    Boolean[][] memo = new Boolean[n + 1][n + 1];
    return dfs(0, 0, s, memo);
}

private boolean dfs(int i, int open, String s, Boolean[][] memo) {
    // Too many closing parens
    if (open < 0) return false;

    // End of string: valid if all matched
    if (i == s.length()) return open == 0;

    // Memoization
    if (memo[i][open] != null) return memo[i][open];

    boolean result;
    if (s.charAt(i) == '(') {
        result = dfs(i + 1, open + 1, s, memo);
    } else if (s.charAt(i) == ')') {
        result = dfs(i + 1, open - 1, s, memo);
    } else { // '*'
        result = dfs(i + 1, open, s, memo) ||        // empty
                 dfs(i + 1, open + 1, s, memo) ||    // '('
                 dfs(i + 1, open - 1, s, memo);      // ')'
    }

    memo[i][open] = result;
    return result;
}

// java
// LC 678 - Valid Parenthesis String
// IDEA: same states as approach 4, filled bottom-up
// time = O(n^2), space = O(n^2)
public boolean checkValidString(String s) {
    int n = s.length();
    boolean[][] dp = new boolean[n + 1][n + 1];
    dp[n][0] = true; // base: end with 0 open parens

    for (int i = n - 1; i >= 0; i--) {
        for (int open = 0; open < n; open++) {
            boolean res = false;
            if (s.charAt(i) == '*') {
                res |= dp[i + 1][open + 1];           // treat as '('
                if (open > 0) res |= dp[i + 1][open - 1]; // treat as ')'
                res |= dp[i + 1][open];                // treat as empty
            } else {
                if (s.charAt(i) == '(') {
                    res |= dp[i + 1][open + 1];
                } else if (open > 0) {
                    res |= dp[i + 1][open - 1];
                }
            }
            dp[i][open] = res;
        }
    }
    return dp[0][0];
}

// java
// LC 678 - Valid Parenthesis String
// IDEA: bottom-up rolled down to one row over `open`
// time = O(n^2), space = O(n)
public boolean checkValidString(String s) {
    int n = s.length();
    boolean[] dp = new boolean[n + 1];
    dp[0] = true;

    for (int i = n - 1; i >= 0; i--) {
        boolean[] newDp = new boolean[n + 1];
        for (int open = 0; open < n; open++) {
            if (s.charAt(i) == '*') {
                newDp[open] = dp[open + 1] ||
                              (open > 0 && dp[open - 1]) ||
                              dp[open];
            } else if (s.charAt(i) == '(') {
                newDp[open] = dp[open + 1];
            } else if (open > 0) {
                newDp[open] = dp[open - 1];
            }
        }
        dp = newDp;
    }
    return dp[0];
}

// java
// LC 678 - Valid Parenthesis String
// IDEA: two stacks — one of '(' indices, one of '*' indices; match leftovers by position
// time = O(n), space = O(n)
public boolean checkValidString(String s) {
    Stack<Integer> leftStack = new Stack<>();  // indices of '('
    Stack<Integer> starStack = new Stack<>();  // indices of '*'

    // First pass: match ')' with '(' or '*'
    for (int i = 0; i < s.length(); i++) {
        char ch = s.charAt(i);
        if (ch == '(') {
            leftStack.push(i);
        } else if (ch == '*') {
            starStack.push(i);
        } else { // ')'
            if (!leftStack.isEmpty()) {
                leftStack.pop();
            } else if (!starStack.isEmpty()) {
                starStack.pop();
            } else {
                return false; // unmatched ')'
            }
        }
    }

    // Second pass: match remaining '(' with '*'
    while (!leftStack.isEmpty() && !starStack.isEmpty()) {
        // '*' must come after '(' to be valid
        if (leftStack.pop() > starStack.pop()) {
            return false;
        }
    }

    return leftStack.isEmpty();
}

every existing subsequence can be extended by ch   ->  `total` brand new candidates
but if ch appeared before, the `add` value it produced back then
generated exactly the same set again                ->  subtract it

add   = total                      # candidates created by this ch
total = total + add - last[ch]     # last[ch] = the `add` from ch's previous occurrence
last[ch] = add

start      total = 1                       { "" }
'a'  add=1 total = 1 + 1 - 0 = 2           { "", a }
'b'  add=2 total = 2 + 2 - 0 = 4           { "", a, b, ab }
'a'  add=4 total = 4 + 4 - 1 = 7           { "", a, b, ab, aa, ba, aba }
answer = 7 - 1 = 6

// java
// LC 940 - Distinct Subsequences II
// IDEA: running count of distinct subsequences incl. the empty one; each character adds
//       `total` new ones and re-creates `last[ch]` old ones, so subtract those.
// time = O(n), space = O(1)  (26 counters)
public int distinctSubseqII(String s) {
    final int MOD = 1_000_000_007;
    long[] last = new long[26];      // last[c] = the `add` produced by c's previous occurrence
    long total = 1;                  // the empty subsequence

    for (char ch : s.toCharArray()) {
        long add = total;
        // NOTE !!! + MOD before the second % — `total + add - last[c]` can go negative
        total = (total + add - last[ch - 'a'] + MOD) % MOD;
        last[ch - 'a'] = add;
    }
    return (int) ((total - 1 + MOD) % MOD);   // drop the empty subsequence
}

# python
# LC 940 - Distinct Subsequences II
# IDEA: same running total; `last[ch]` remembers what this character contributed last time
# time = O(n), space = O(1)
def distinctSubseqII(s):
    MOD = 10 ** 9 + 7
    last = {}
    total = 1                        # counts the empty subsequence

    for ch in s:
        add = total                  # every current subsequence can be extended by ch
        total = (total + add - last.get(ch, 0)) % MOD
        last[ch] = add

    return (total - 1) % MOD         # exclude the empty subsequence