String DP Patterns: Complete Reference¶

def string_dp_template(s: str, t: str) -> int:
    """
    Generic String DP template.

    Key components:
    1. State: dp[i][j] = solution for s[0:i] and t[0:j]
    2. Base Case: Initialize dp[0][*] and dp[*][0]
    3. Transition: Define how dp[i][j] relates to dp[i-1][j-1], dp[i-1][j], dp[i][j-1]
    4. Answer: Usually dp[m][n] where m, n are string lengths
    """
    m, n = len(s), len(t)

    # State table with (m+1) x (n+1) dimensions for empty string handling
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    # BASE CASE: Initialize first row and column
    for i in range(m + 1):
        dp[i][0] = base_case_s(i)
    for j in range(n + 1):
        dp[0][j] = base_case_t(j)

    # TRANSITION: Fill table row by row
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s[i - 1] == t[j - 1]:
                # Characters match: inherit from diagonal
                dp[i][j] = match_transition(dp[i - 1][j - 1])
            else:
                # Characters differ: combine from all directions
                dp[i][j] = mismatch_transition(
                    dp[i - 1][j - 1],  # diagonal (substitute)
                    dp[i - 1][j],      # up (operation on s)
                    dp[i][j - 1]       # left (operation on t)
                )

    return dp[m][n]

def string_dp_space_optimized(s: str, t: str) -> int:
    m, n = len(s), len(t)

    # Only keep current and previous row
    prev = [base_case_t(j) for j in range(n + 1)]
    curr = [0] * (n + 1)

    for i in range(1, m + 1):
        curr[0] = base_case_s(i)
        for j in range(1, n + 1):
            if s[i - 1] == t[j - 1]:
                curr[j] = match_transition(prev[j - 1])
            else:
                curr[j] = mismatch_transition(prev[j - 1], prev[j], curr[j - 1])
        prev, curr = curr, prev

    return prev[n]

class SolutionLCS:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        """
        Find the longest common subsequence of two strings.

        Algorithm:
        - Build 2D DP table where dp[i][j] = LCS length for text1[0:i], text2[0:j]
        - When characters match: extend LCS from diagonal
        - When they don't: take best of skipping either character

        Time: O(m * n) where m, n are string lengths
        Space: O(m * n), can be optimized to O(min(m, n))
        """
        string_length_1, string_length_2 = len(text1), len(text2)

        # dp[i][j] = LCS length for text1[0:i] and text2[0:j]
        # Extra row/column for empty string base cases
        lcs_table: list[list[int]] = [
            [0] * (string_length_2 + 1)
            for _ in range(string_length_1 + 1)
        ]

        # Base case: LCS with empty string is 0 (already initialized)

        # Fill table: compare each character pair
        for idx_1 in range(1, string_length_1 + 1):
            for idx_2 in range(1, string_length_2 + 1):
                char_1 = text1[idx_1 - 1]
                char_2 = text2[idx_2 - 1]

                if char_1 == char_2:
                    # Characters match: extend LCS from previous diagonal
                    lcs_table[idx_1][idx_2] = lcs_table[idx_1 - 1][idx_2 - 1] + 1
                else:
                    # No match: take best of skipping either character
                    skip_from_text1 = lcs_table[idx_1 - 1][idx_2]
                    skip_from_text2 = lcs_table[idx_1][idx_2 - 1]
                    lcs_table[idx_1][idx_2] = max(skip_from_text1, skip_from_text2)

        return lcs_table[string_length_1][string_length_2]

class SolutionLCSOptimized:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        """
        Space-optimized LCS using two rows instead of full table.

        Key insight: Each cell only depends on:
        - Previous row, same column (up)
        - Same row, previous column (left)
        - Previous row, previous column (diagonal)

        Time: O(m * n)
        Space: O(min(m, n))
        """
        # Ensure text2 is the shorter string for space optimization
        if len(text1) < len(text2):
            text1, text2 = text2, text1

        string_length_2 = len(text2)

        # Only need previous row and current row
        previous_row: list[int] = [0] * (string_length_2 + 1)
        current_row: list[int] = [0] * (string_length_2 + 1)

        for idx_1, char_1 in enumerate(text1, 1):
            for idx_2, char_2 in enumerate(text2, 1):
                if char_1 == char_2:
                    # Match: extend from diagonal (previous row, previous column)
                    current_row[idx_2] = previous_row[idx_2 - 1] + 1
                else:
                    # No match: max of up (previous row) and left (current row)
                    current_row[idx_2] = max(previous_row[idx_2], current_row[idx_2 - 1])

            # Swap rows for next iteration
            previous_row, current_row = current_row, previous_row

        return previous_row[string_length_2]

class SolutionEditDistance:
    def minDistance(self, word1: str, word2: str) -> int:
        """
        Calculate minimum edit distance (Levenshtein distance) between two strings.

        The three operations and their DP transitions:
        - Replace: dp[i-1][j-1] + 1 (transform word1[i-1] to word2[j-1])
        - Delete:  dp[i-1][j] + 1   (remove word1[i-1])
        - Insert:  dp[i][j-1] + 1   (add word2[j-1] to word1)

        Time: O(m * n)
        Space: O(m * n), can be optimized to O(n)
        """
        source_length = len(word1)
        target_length = len(word2)

        # dp[i][j] = min operations to convert word1[0:i] to word2[0:j]
        edit_distance: list[list[int]] = [
            [0] * (target_length + 1)
            for _ in range(source_length + 1)
        ]

        # Base case: converting to/from empty string
        # Empty -> word2[0:j] requires j insertions
        for j in range(target_length + 1):
            edit_distance[0][j] = j

        # word1[0:i] -> empty requires i deletions
        for i in range(source_length + 1):
            edit_distance[i][0] = i

        # Fill table with minimum operations
        for i in range(1, source_length + 1):
            for j in range(1, target_length + 1):
                source_char = word1[i - 1]
                target_char = word2[j - 1]

                if source_char == target_char:
                    # Characters match: no operation needed
                    edit_distance[i][j] = edit_distance[i - 1][j - 1]
                else:
                    # Take minimum of three operations
                    replace_cost = edit_distance[i - 1][j - 1] + 1
                    delete_cost = edit_distance[i - 1][j] + 1
                    insert_cost = edit_distance[i][j - 1] + 1

                    edit_distance[i][j] = min(replace_cost, delete_cost, insert_cost)

        return edit_distance[source_length][target_length]

class SolutionEditDistanceOptimized:
    def minDistance(self, word1: str, word2: str) -> int:
        """
        Space-optimized edit distance using single row + diagonal variable.

        Tricky part: We need dp[i-1][j-1] (diagonal) but we're overwriting it.
        Solution: Save diagonal before overwriting.

        Time: O(m * n)
        Space: O(n)
        """
        source_length = len(word1)
        target_length = len(word2)

        # Previous row: represents dp[i-1][*]
        previous_row: list[int] = list(range(target_length + 1))

        for i in range(1, source_length + 1):
            # Save dp[i-1][0] before overwriting (needed for diagonal)
            diagonal = previous_row[0]
            previous_row[0] = i  # Base case: i deletions

            for j in range(1, target_length + 1):
                # Save current value (will be diagonal for next iteration)
                next_diagonal = previous_row[j]

                if word1[i - 1] == word2[j - 1]:
                    previous_row[j] = diagonal
                else:
                    previous_row[j] = 1 + min(
                        diagonal,           # replace
                        previous_row[j],    # delete (was dp[i-1][j])
                        previous_row[j - 1] # insert
                    )

                diagonal = next_diagonal

        return previous_row[target_length]

class SolutionLPSviaLCS:
    def longestPalindromeSubseq(self, s: str) -> int:
        """
        Reduce to LCS: Longest palindromic subsequence equals
        LCS of string with its reverse.

        Intuition: A palindrome reads the same forward and backward.
        The common subsequence of s and reverse(s) is palindromic.

        Time: O(n^2)
        Space: O(n)
        """
        reversed_string = s[::-1]
        string_length = len(s)

        # Space-optimized LCS
        previous_row: list[int] = [0] * (string_length + 1)

        for idx_original in range(1, string_length + 1):
            current_row: list[int] = [0] * (string_length + 1)
            for idx_reversed in range(1, string_length + 1):
                if s[idx_original - 1] == reversed_string[idx_reversed - 1]:
                    current_row[idx_reversed] = previous_row[idx_reversed - 1] + 1
                else:
                    current_row[idx_reversed] = max(
                        previous_row[idx_reversed],
                        current_row[idx_reversed - 1]
                    )
            previous_row = current_row

        return previous_row[string_length]

class SolutionLPSInterval:
    def longestPalindromeSubseq(self, s: str) -> int:
        """
        Direct interval DP approach.

        State: dp[i][j] = LPS length for substring s[i:j+1]
        Transition:
        - If s[i] == s[j]: dp[i][j] = dp[i+1][j-1] + 2
        - Else: dp[i][j] = max(dp[i+1][j], dp[i][j-1])

        Key insight: Fill table by increasing interval length.

        Time: O(n^2)
        Space: O(n^2), can be optimized to O(n)
        """
        string_length = len(s)

        if string_length <= 1:
            return string_length

        # dp[i][j] = LPS length for s[i:j+1]
        palindrome_length: list[list[int]] = [
            [0] * string_length
            for _ in range(string_length)
        ]

        # Base case: single character is palindrome of length 1
        for i in range(string_length):
            palindrome_length[i][i] = 1

        # Fill by increasing interval length
        for interval_length in range(2, string_length + 1):
            for start in range(string_length - interval_length + 1):
                end = start + interval_length - 1

                if s[start] == s[end]:
                    # Endpoints match: extend inner palindrome by 2
                    inner_length = palindrome_length[start + 1][end - 1] if start + 1 <= end - 1 else 0
                    palindrome_length[start][end] = inner_length + 2
                else:
                    # Endpoints don't match: take best of excluding either
                    exclude_start = palindrome_length[start + 1][end]
                    exclude_end = palindrome_length[start][end - 1]
                    palindrome_length[start][end] = max(exclude_start, exclude_end)

        return palindrome_length[0][string_length - 1]

class SolutionLPSOptimized:
    def longestPalindromeSubseq(self, s: str) -> int:
        """
        Space-optimized: Only need previous diagonal values.

        We iterate by interval length, so we only need values from
        the previous length. Use 1D array with careful update order.

        Time: O(n^2)
        Space: O(n)
        """
        string_length = len(s)

        # dp[j] = LPS length ending at position j for current start
        current_row: list[int] = [1] * string_length

        for start in range(string_length - 2, -1, -1):
            # previous_diagonal saves dp[start+1][end-1] before overwrite
            previous_diagonal = 0

            for end in range(start + 1, string_length):
                # Save current value (will be diagonal for next end)
                temp = current_row[end]

                if s[start] == s[end]:
                    current_row[end] = previous_diagonal + 2
                else:
                    current_row[end] = max(current_row[end], current_row[end - 1])

                previous_diagonal = temp

        return current_row[string_length - 1]

class SolutionRegex:
    def isMatch(self, s: str, p: str) -> bool:
        """
        Implement regular expression matching with '.' and '*'.

        The '*' operator is the key challenge:
        - It modifies the PRECEDING character
        - It can match zero or more occurrences
        - We must consider both "use it" and "skip it" cases

        Time: O(m * n) where m = len(s), n = len(p)
        Space: O(m * n)
        """
        text_length = len(s)
        pattern_length = len(p)

        # dp[i][j] = True if s[0:i] matches p[0:j]
        is_match: list[list[bool]] = [
            [False] * (pattern_length + 1)
            for _ in range(text_length + 1)
        ]

        # Base case: empty string matches empty pattern
        is_match[0][0] = True

        # Base case: empty string vs pattern with '*'
        # Pattern like "a*b*c*" can match empty string
        for j in range(2, pattern_length + 1):
            if p[j - 1] == '*':
                # '*' can eliminate its preceding character
                is_match[0][j] = is_match[0][j - 2]

        # Fill DP table
        for i in range(1, text_length + 1):
            for j in range(1, pattern_length + 1):
                pattern_char = p[j - 1]

                if pattern_char == '*':
                    # Get the character before '*'
                    preceding_char = p[j - 2]

                    # Option 1: Use zero occurrences (skip char + '*')
                    zero_match = is_match[i][j - 2]

                    # Option 2: Use one+ occurrences (if current char matches preceding)
                    char_matches = (preceding_char == '.' or preceding_char == s[i - 1])
                    one_or_more_match = char_matches and is_match[i - 1][j]

                    is_match[i][j] = zero_match or one_or_more_match

                elif pattern_char == '.' or pattern_char == s[i - 1]:
                    # Direct match: inherit from diagonal
                    is_match[i][j] = is_match[i - 1][j - 1]

                # else: mismatch, stays False

        return is_match[text_length][pattern_length]

class SolutionRegexOptimized:
    def isMatch(self, s: str, p: str) -> bool:
        """
        Space-optimized regex matching using two rows.

        Key insight: Each cell depends on:
        - Same row, j-2 (for '*' zero match)
        - Previous row, j (for '*' one+ match)
        - Previous row, j-1 (for direct match)

        Time: O(m * n)
        Space: O(n)
        """
        text_length = len(s)
        pattern_length = len(p)

        previous_row: list[bool] = [False] * (pattern_length + 1)
        previous_row[0] = True

        # Initialize: empty string vs pattern
        for j in range(2, pattern_length + 1):
            if p[j - 1] == '*':
                previous_row[j] = previous_row[j - 2]

        for i in range(1, text_length + 1):
            current_row: list[bool] = [False] * (pattern_length + 1)
            # current_row[0] = False (non-empty string can't match empty pattern)

            for j in range(1, pattern_length + 1):
                pattern_char = p[j - 1]

                if pattern_char == '*':
                    preceding_char = p[j - 2]

                    zero_match = current_row[j - 2]
                    char_matches = (preceding_char == '.' or preceding_char == s[i - 1])
                    one_or_more_match = char_matches and previous_row[j]

                    current_row[j] = zero_match or one_or_more_match

                elif pattern_char == '.' or pattern_char == s[i - 1]:
                    current_row[j] = previous_row[j - 1]

            previous_row = current_row

        return previous_row[pattern_length]

class SolutionWildcard:
    def isMatch(self, s: str, p: str) -> bool:
        """
        Implement wildcard pattern matching with '?' and '*'.

        Key insight for '*':
        - '*' can match empty: dp[i][j-1]
        - '*' can match current char and more: dp[i-1][j]

        The second case is powerful: if s[0:i-1] matches p[0:j],
        then s[0:i] also matches because '*' can extend.

        Time: O(m * n)
        Space: O(m * n)
        """
        text_length = len(s)
        pattern_length = len(p)

        # dp[i][j] = True if s[0:i] matches p[0:j]
        is_match: list[list[bool]] = [
            [False] * (pattern_length + 1)
            for _ in range(text_length + 1)
        ]

        # Base case: empty matches empty
        is_match[0][0] = True

        # Base case: empty string can match pattern of only '*'s
        for j in range(1, pattern_length + 1):
            if p[j - 1] == '*':
                is_match[0][j] = is_match[0][j - 1]
            else:
                break  # Once we hit non-'*', no more matches possible

        # Fill DP table
        for i in range(1, text_length + 1):
            for j in range(1, pattern_length + 1):
                pattern_char = p[j - 1]
                text_char = s[i - 1]

                if pattern_char == '*':
                    # '*' matches empty OR '*' matches current char and continues
                    match_empty = is_match[i][j - 1]
                    match_one_more = is_match[i - 1][j]
                    is_match[i][j] = match_empty or match_one_more

                elif pattern_char == '?' or pattern_char == text_char:
                    # Direct match: carry result from diagonal
                    is_match[i][j] = is_match[i - 1][j - 1]

                # else: mismatch, stays False

        return is_match[text_length][pattern_length]

class SolutionWildcardGreedy:
    def isMatch(self, s: str, p: str) -> bool:
        """
        Greedy approach with backtracking on '*'.

        Strategy:
        - Match character by character
        - When hitting '*', remember position and try matching empty first
        - If later mismatch, backtrack to last '*' and match one more char

        Time: O(m * n) worst case, O(m + n) average
        Space: O(1)
        """
        text_idx = 0
        pattern_idx = 0
        text_length = len(s)
        pattern_length = len(p)

        # Position of last '*' and corresponding text position
        last_star_idx = -1
        last_star_match = 0

        while text_idx < text_length:
            # Case 1: Characters match or '?'
            if (pattern_idx < pattern_length and
                (p[pattern_idx] == s[text_idx] or p[pattern_idx] == '?')):
                text_idx += 1
                pattern_idx += 1

            # Case 2: '*' found - remember and match empty initially
            elif pattern_idx < pattern_length and p[pattern_idx] == '*':
                last_star_idx = pattern_idx
                last_star_match = text_idx
                pattern_idx += 1  # Move past '*', match empty

            # Case 3: Mismatch - backtrack to last '*' if exists
            elif last_star_idx != -1:
                pattern_idx = last_star_idx + 1
                last_star_match += 1  # '*' matches one more char
                text_idx = last_star_match

            else:
                return False

        # Skip trailing '*' in pattern
        while pattern_idx < pattern_length and p[pattern_idx] == '*':
            pattern_idx += 1

        return pattern_idx == pattern_length

def lcs(s: str, t: str) -> int:
    """
    Find the length of the longest common subsequence.
    Time: O(m*n), Space: O(m*n)
    """
    m, n = len(s), len(t)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s[i-1] == t[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])

    return dp[m][n]

def edit_distance(s: str, t: str) -> int:
    """
    Find minimum operations to convert s to t.
    Operations: insert, delete, replace.
    Time: O(m*n), Space: O(m*n)
    """
    m, n = len(s), len(t)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    # Base cases
    for i in range(m + 1):
        dp[i][0] = i
    for j in range(n + 1):
        dp[0][j] = j

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s[i-1] == t[j-1]:
                dp[i][j] = dp[i-1][j-1]
            else:
                dp[i][j] = 1 + min(
                    dp[i-1][j-1],  # replace
                    dp[i-1][j],    # delete
                    dp[i][j-1]     # insert
                )

    return dp[m][n]

def regex_match(s: str, p: str) -> bool:
    """
    Match string s against pattern p with . and * wildcards.
    Time: O(m*n), Space: O(m*n)
    """
    m, n = len(s), len(p)
    dp = [[False] * (n + 1) for _ in range(m + 1)]
    dp[0][0] = True

    # Handle patterns like a*, a*b*, etc. matching empty string
    for j in range(2, n + 1):
        if p[j-1] == '*':
            dp[0][j] = dp[0][j-2]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if p[j-1] == '*':
                # Zero occurrences of preceding char
                dp[i][j] = dp[i][j-2]
                # One or more if matching
                if p[j-2] == '.' or p[j-2] == s[i-1]:
                    dp[i][j] = dp[i][j] or dp[i-1][j]
            elif p[j-1] == '.' or p[j-1] == s[i-1]:
                dp[i][j] = dp[i-1][j-1]

    return dp[m][n]

def lcs_optimized(s: str, t: str) -> int:
    """
    Space-optimized LCS using O(n) space.
    Time: O(m*n), Space: O(min(m,n))
    """
    if len(s) < len(t):
        s, t = t, s
    m, n = len(s), len(t)

    prev = [0] * (n + 1)
    curr = [0] * (n + 1)

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s[i-1] == t[j-1]:
                curr[j] = prev[j-1] + 1
            else:
                curr[j] = max(prev[j], curr[j-1])
        prev, curr = curr, prev

    return prev[n]