Menu

Earn Premium with Referrals

Invite your friends and earn Premium rewards through our referral program.

See how it works and start inviting friends.

String DP
DSA

String DP

Learn DP techniques for string matching, subsequences, transformations, and comparison problems.

String DP is one of the most important Dynamic Programming categories in interviews and competitive programming.

At its core, String DP asks:

“How are prefixes, substrings, or subsequences of strings related?”

Most String DP problems fall into a few reusable families:

Compare two strings → LCS-style DP

Transform one string into another → Edit Distance DP

Count ways to form a string → Subsequences / Prefix Counting DP

Analyze symmetry → Palindrome DP

Split a string → Partition / Interval DP

Match a pattern → Pattern Matching DP

Build or segment a string → Prefix DP

The most important skill is not memorizing individual problems.

It is recognizing what the DP indices represent.

Pattern Table

PatternStateTypical QuestionsMain Trigger
LCSdp[i][j]Longest common subsequenceTwo strings + common subsequence
Longest Common Substringdp[i][j]Longest continuous matchTwo strings + contiguous
Edit Distancedp[i][j]Transform stringInsert/Delete/Replace
Distinct Subsequencesdp[i][j]Count target formationsCount subsequences
Palindrome DPdp[i][j]Palindrome checks/optimizationSymmetry
Decode Waysdp[i]Count decodings1-digit / 2-digit choices
Wildcard Matchingdp[i][j]? / * matchingPattern matching
Regex Matchingdp[i][j]. / * matchingRegex rules
Shortest Common Supersequencedp[i][j]Merge two stringsLCS extension
Interleaving Stringdp[i][j]Form third stringTwo-source prefix DP
Word Breakdp[i]Dictionary segmentationPrefix feasibility
Palindrome Partitioningdp[i] / dp[i][j]Minimum palindrome cutsString partitioning

1. Longest Common Subsequence (LCS)

Two strings meet in one grid — shared letters walk diagonally, misses inherit the best neighbour:

Longest Common Subsequence

Length of the longest subsequence shared by two strings.

dp[i][j] over prefixes. If s1[i]==s2[j] take the diagonal +1; else inherit max(up, left). Matches trace diagonals, mismatches take the better neighbour. O(n·m) time and space.

GRID VISUALIZER
Steps –
0
0
0
0
0
·
·
·
0
·
·
·
0
·
·
·
Press ▶ to animate, or step through manually.
Variables
keys: ← → space F
Pseudocode

                        1
                        dp[i][j] = LCS of s1[0..i-1] and s2[0..j-1]
                      
                        2
                        if s1[i-1] == s2[j-1]: dp[i][j] = 1 + dp[i-1][j-1]
                      
                        3
                        else: dp[i][j] = max(dp[i-1][j], dp[i][j-1])
                      
                        4
                        return dp[n][m]

Detection

Use LCS when:

  • There are two strings/sequences.
  • Characters must remain in order.
  • Characters can be skipped.
  • You want the longest/common/optimal subsequence.

Important distinction

Subsequence:
A B C D
↑   ↑
Can skip characters.

Substring:
A B C D
  ↑ ↑
Must be continuous.

State

dp[i][j]
=
LCS length between
first i characters of s1
and first j characters of s2

Transition

If characters match:

dp[i][j] = 1 + dp[i-1][j-1]

Otherwise:

dp[i][j] =
max(
    dp[i-1][j],
    dp[i][j-1]
)

Java Template

public static int lcs(String s1, String s2) {
    int n = s1.length();
    int m = s2.length();

    int[][] dp = new int[n + 1][m + 1];

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {

            if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                dp[i][j] = 1 + dp[i - 1][j - 1];
            } else {
                dp[i][j] = Math.max(
                    dp[i - 1][j],
                    dp[i][j - 1]
                );
            }
        }
    }

    return dp[n][m];
}
def lcs(s1, s2):
    n = len(s1)
    m = len(s2)

    dp = [[0] * (m + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for j in range(1, m + 1):

            if s1[i - 1] == s2[j - 1]:
                dp[i][j] = 1 + dp[i - 1][j - 1]
            else:
                dp[i][j] = max(
                    dp[i - 1][j],
                    dp[i][j - 1]
                )

    return dp[n][m]
int lcs(string& s1, string& s2) {
    int n = s1.size();
    int m = s2.size();

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

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {

            if (s1[i - 1] == s2[j - 1]) {
                dp[i][j] = 1 + dp[i - 1][j - 1];
            } else {
                dp[i][j] = max(
                    dp[i - 1][j],
                    dp[i][j - 1]
                );
            }
        }
    }

    return dp[n][m];
}
function lcs(s1, s2) {
  const n = s1.length;
  const m = s2.length;

  const dp = Array.from({ length: n + 1 }, () =>
    new Array(m + 1).fill(0)
  );

  for (let i = 1; i <= n; i++) {
    for (let j = 1; j <= m; j++) {
      if (s1[i - 1] === s2[j - 1]) {
        dp[i][j] = 1 + dp[i - 1][j - 1];
      } else {
        dp[i][j] = Math.max(
          dp[i - 1][j],
          dp[i][j - 1]
        );
      }
    }
  }

  return dp[n][m];
}

Space Optimized Java

public static int lcs(String s1, String s2) {
    int n = s1.length();
    int m = s2.length();

    int[] prev = new int[m + 1];
    int[] curr = new int[m + 1];

    for (int i = 1; i <= n; i++) {

        for (int j = 1; j <= m; j++) {

            if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                curr[j] = 1 + prev[j - 1];
            } else {
                curr[j] = Math.max(
                    prev[j],
                    curr[j - 1]
                );
            }
        }

        int[] temp = prev;
        prev = curr;
        curr = temp;
    }

    return prev[m];
}
def lcs(s1, s2):
    n = len(s1)
    m = len(s2)

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

    for i in range(1, n + 1):

        for j in range(1, m + 1):

            if s1[i - 1] == s2[j - 1]:
                curr[j] = 1 + prev[j - 1]
            else:
                curr[j] = max(
                    prev[j],
                    curr[j - 1]
                )

        prev, curr = curr, prev

    return prev[m]
int lcs(string& s1, string& s2) {
    int n = s1.size();
    int m = s2.size();

    vector<int> prev(m + 1);
    vector<int> curr(m + 1);

    for (int i = 1; i <= n; i++) {

        for (int j = 1; j <= m; j++) {

            if (s1[i - 1] == s2[j - 1]) {
                curr[j] = 1 + prev[j - 1];
            } else {
                curr[j] = max(
                    prev[j],
                    curr[j - 1]
                );
            }
        }

        swap(prev, curr);
    }

    return prev[m];
}
function lcs(s1, s2) {
  const n = s1.length;
  const m = s2.length;

  let prev = new Array(m + 1).fill(0);
  let curr = new Array(m + 1).fill(0);

  for (let i = 1; i <= n; i++) {
    for (let j = 1; j <= m; j++) {
      if (s1[i - 1] === s2[j - 1]) {
        curr[j] = 1 + prev[j - 1];
      } else {
        curr[j] = Math.max(
          prev[j],
          curr[j - 1]
        );
      }
    }

    const temp = prev;
    prev = curr;
    curr = temp;
  }

  return prev[m];
}

Mental Trigger

Two sequences + preserve order + skipping allowed → LCS

2. Longest Common Substring

This looks almost identical to LCS, but there is one critical difference.

LCS vs Longest Common Substring

FeatureLCSCommon Substring
Skip charactersYesNo
Must be continuousNoYes
Mismatch transitionTake maxReset to 0
StatePrefix comparisonEnding match

State

dp[i][j]
=
length of common substring
ending at s1[i-1] and s2[j-1]

Transition

if equal:

    dp[i][j] = 1 + dp[i-1][j-1]

else:

    dp[i][j] = 0

Keep the global maximum.

Java Template

public static int longestCommonSubstring(String s1, String s2) {
    int n = s1.length();
    int m = s2.length();

    int[][] dp = new int[n + 1][m + 1];

    int answer = 0;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {

            if (s1.charAt(i - 1) == s2.charAt(j - 1)) {

                dp[i][j] =
                    1 + dp[i - 1][j - 1];

                answer = Math.max(
                    answer,
                    dp[i][j]
                );

            } else {
                dp[i][j] = 0;
            }
        }
    }

    return answer;
}
def longest_common_substring(s1, s2):
    n = len(s1)
    m = len(s2)

    dp = [[0] * (m + 1) for _ in range(n + 1)]

    answer = 0

    for i in range(1, n + 1):
        for j in range(1, m + 1):

            if s1[i - 1] == s2[j - 1]:

                dp[i][j] = 1 + dp[i - 1][j - 1]

                answer = max(answer, dp[i][j])

            else:
                dp[i][j] = 0

    return answer
int longestCommonSubstring(string& s1, string& s2) {
    int n = s1.size();
    int m = s2.size();

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

    int answer = 0;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {

            if (s1[i - 1] == s2[j - 1]) {

                dp[i][j] =
                    1 + dp[i - 1][j - 1];

                answer = max(
                    answer,
                    dp[i][j]
                );

            } else {
                dp[i][j] = 0;
            }
        }
    }

    return answer;
}
function longestCommonSubstring(s1, s2) {
  const n = s1.length;
  const m = s2.length;

  const dp = Array.from({ length: n + 1 }, () =>
    new Array(m + 1).fill(0)
  );

  let answer = 0;

  for (let i = 1; i <= n; i++) {
    for (let j = 1; j <= m; j++) {
      if (s1[i - 1] === s2[j - 1]) {
        dp[i][j] = 1 + dp[i - 1][j - 1];

        answer = Math.max(answer, dp[i][j]);
      } else {
        dp[i][j] = 0;
      }
    }
  }

  return answer;
}

Mental Trigger

Two strings + continuous matching → Longest Common Substring

3. Edit Distance

Edit Distance asks:

What is the minimum number of operations required to convert one string into another?

Allowed operations:

Insert
Delete
Replace

State

dp[i][j]
=
minimum operations required
to convert first i characters of s1
into first j characters of s2

Transition

If characters are equal:

dp[i][j] = dp[i-1][j-1]

Otherwise:

dp[i][j] =
1 + min(
    insert,
    delete,
    replace
)

where:

insert  = dp[i][j-1]
delete  = dp[i-1][j]
replace = dp[i-1][j-1]

Java Template

public static int editDistance(String s1, String s2) {
    int n = s1.length();
    int m = s2.length();

    int[][] dp = new int[n + 1][m + 1];

    // Convert empty s1 -> first j characters of s2
    for (int j = 0; j <= m; j++) {
        dp[0][j] = j;
    }

    // Convert first i characters of s1 -> empty s2
    for (int i = 0; i <= n; i++) {
        dp[i][0] = i;
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {

            if (s1.charAt(i - 1) == s2.charAt(j - 1)) {

                dp[i][j] = dp[i - 1][j - 1];

            } else {

                int insert = dp[i][j - 1];
                int delete = dp[i - 1][j];
                int replace = dp[i - 1][j - 1];

                dp[i][j] =
                    1 + Math.min(
                        replace,
                        Math.min(insert, delete)
                    );
            }
        }
    }

    return dp[n][m];
}
def edit_distance(s1, s2):
    n = len(s1)
    m = len(s2)

    dp = [[0] * (m + 1) for _ in range(n + 1)]

    # Convert empty s1 -> first j characters of s2
    for j in range(m + 1):
        dp[0][j] = j

    # Convert first i characters of s1 -> empty s2
    for i in range(n + 1):
        dp[i][0] = i

    for i in range(1, n + 1):
        for j in range(1, m + 1):

            if s1[i - 1] == s2[j - 1]:

                dp[i][j] = dp[i - 1][j - 1]

            else:
                insert = dp[i][j - 1]
                delete = dp[i - 1][j]
                replace = dp[i - 1][j - 1]

                dp[i][j] = 1 + min(
                    replace,
                    insert,
                    delete
                )

    return dp[n][m]
int editDistance(string& s1, string& s2) {
    int n = s1.size();
    int m = s2.size();

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

    // Convert empty s1 -> first j characters of s2
    for (int j = 0; j <= m; j++) {
        dp[0][j] = j;
    }

    // Convert first i characters of s1 -> empty s2
    for (int i = 0; i <= n; i++) {
        dp[i][0] = i;
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {

            if (s1[i - 1] == s2[j - 1]) {

                dp[i][j] = dp[i - 1][j - 1];

            } else {

                int insert = dp[i][j - 1];
                int del = dp[i - 1][j];
                int replace = dp[i - 1][j - 1];

                dp[i][j] =
                    1 + min(
                        replace,
                        min(insert, del)
                    );
            }
        }
    }

    return dp[n][m];
}
function editDistance(s1, s2) {
  const n = s1.length;
  const m = s2.length;

  const dp = Array.from({ length: n + 1 }, () =>
    new Array(m + 1).fill(0)
  );

  // Convert empty s1 -> first j characters of s2
  for (let j = 0; j <= m; j++) {
    dp[0][j] = j;
  }

  // Convert first i characters of s1 -> empty s2
  for (let i = 0; i <= n; i++) {
    dp[i][0] = i;
  }

  for (let i = 1; i <= n; i++) {
    for (let j = 1; j <= m; j++) {
      if (s1[i - 1] === s2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1];
      } else {
        const insert = dp[i][j - 1];
        const del = dp[i - 1][j];
        const replace = dp[i - 1][j - 1];

        dp[i][j] =
          1 +
          Math.min(
            replace,
            Math.min(insert, del)
          );
      }
    }
  }

  return dp[n][m];
}

Edit Distance

Minimum insert/delete/replace ops to turn one string into another.

dp[i][j] = ops for first i of s1, first j of s2. Match → dp[i-1][j-1]; else 1 + min(insert dp[i][j-1], delete dp[i-1][j], replace dp[i-1][j-1]). The table fills by comparing characters cell by cell. O(n·m) time and space.

GRID VISUALIZER
Steps –
0
1
2
3
1
0
1
2
2
1
0
1
3
2
1
1
Press ▶ to animate, or step through manually.
Variables
keys: ← → space F
Pseudocode

                        1
                        dp[i][j] = min ops to convert s1[0..i-1] to s2[0..j-1]
                      
                        2
                        if s1[i-1] == s2[j-1]: dp[i][j] = dp[i-1][j-1]
                      
                        3
                        else: dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
                      
                        4
                        return dp[n][m]

Mental Trigger

Convert string A → string B → Edit Distance

4. Distinct Subsequences

This is a counting DP, unlike LCS which is an optimization DP.

Question:

How many subsequences of s equal t?

Key idea

At every character we have a choice:

Skip s[i]

or, if characters match:

Use s[i]

State

dp[i][j]
=
number of ways to form
first j characters of t
using first i characters of s

Transition

If characters match:

dp[i][j]
=
dp[i-1][j-1]
+
dp[i-1][j]

Otherwise:

dp[i][j] = dp[i-1][j]

Java Template

public static long distinctSubsequences(String s, String t) {
    int n = s.length();
    int m = t.length();

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

    // Empty target can always be formed.
    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.charAt(i - 1) == t.charAt(j - 1)) {
                dp[i][j] += dp[i - 1][j - 1];
            }
        }
    }

    return dp[n][m];
}
def distinct_subsequences(s, t):
    n = len(s)
    m = len(t)

    dp = [[0] * (m + 1) for _ in range(n + 1)]

    # Empty target can always be formed.
    for i in range(n + 1):
        dp[i][0] = 1

    for i in range(1, n + 1):
        for j in range(1, m + 1):

            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]
long long distinctSubsequences(string& s, string& t) {
    int n = s.size();
    int m = t.size();

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

    // Empty target can always be formed.
    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];
}
function distinctSubsequences(s, t) {
  const n = s.length;
  const m = t.length;

  const dp = Array.from({ length: n + 1 }, () =>
    new Array(m + 1).fill(0)
  );

  // Empty target can always be formed.
  for (let i = 0; i <= n; i++) {
    dp[i][0] = 1;
  }

  for (let i = 1; i <= n; i++) {
    for (let 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];
}

In problems with a required modulus, perform the additions modulo MOD.

Mental Trigger

Count ways to form target using a source subsequence → Distinct Subsequences

5. Palindrome DP

Palindrome problems are different from LCS.

Instead of comparing two strings, we usually analyze one string over a range.

State

dp[i][j]
=
whether s[i...j] is a palindrome

Transition

A substring is a palindrome when:

s[i] == s[j]

and the inside is also a palindrome.

dp[i][j]
=
s[i] == s[j]
&&
(
    j - i <= 2
    ||
    dp[i + 1][j - 1]
)

Java Template

public static boolean[][] palindromeTable(String s) {
    int n = s.length();

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

    for (int i = n - 1; i >= 0; i--) {

        for (int j = i; j < n; j++) {

            if (s.charAt(i) == s.charAt(j)
                    && (j - i <= 2 || dp[i + 1][j - 1])) {

                dp[i][j] = true;
            }
        }
    }

    return dp;
}
def palindrome_table(s):
    n = len(s)

    dp = [[False] * n for _ in range(n)]

    for i in range(n - 1, -1, -1):

        for j in range(i, n):

            if s[i] == s[j] and (
                j - i <= 2 or dp[i + 1][j - 1]
            ):
                dp[i][j] = True

    return dp
vector<vector<bool>> palindromeTable(string& s) {
    int n = s.size();

    vector<vector<bool>> dp(n, vector<bool>(n));

    for (int i = n - 1; i >= 0; i--) {

        for (int j = i; j < n; j++) {

            if (s[i] == s[j]
                    && (j - i <= 2 || dp[i + 1][j - 1])) {

                dp[i][j] = true;
            }
        }
    }

    return dp;
}
function palindromeTable(s) {
  const n = s.length;

  const dp = Array.from({ length: n }, () =>
    new Array(n).fill(false)
  );

  for (let i = n - 1; i >= 0; i--) {
    for (let j = i; j < n; j++) {
      if (
        s[i] === s[j] &&
        (j - i <= 2 || dp[i + 1][j - 1])
      ) {
        dp[i][j] = true;
      }
    }
  }

  return dp;
}

Why iterate i backwards?

Because:

dp[i][j]

depends on:

dp[i+1][j-1]

So the smaller inner interval must already be calculated.

Mental Trigger

One string + symmetric range → Palindrome DP

6. Decode Ways

Decode Ways is a 1-dimensional string DP.

Example:

1 → A
2 → B
...
26 → Z

At each position we consider:

One digit
Two digits

State

dp[i]
=
number of ways to decode
the first i characters

Java Template

public static int decodeWays(String s) {
    int n = s.length();

    if (n == 0 || s.charAt(0) == '0') {
        return 0;
    }

    int[] dp = new int[n + 1];

    dp[0] = 1;
    dp[1] = 1;

    for (int i = 2; i <= n; i++) {

        char current = s.charAt(i - 1);
        char previous = s.charAt(i - 2);

        // One-digit decoding
        if (current != '0') {
            dp[i] += dp[i - 1];
        }

        // Two-digit decoding
        int number =
            (previous - '0') * 10
            + (current - '0');

        if (number >= 10 && number <= 26) {
            dp[i] += dp[i - 2];
        }
    }

    return dp[n];
}
def decode_ways(s):
    n = len(s)

    if n == 0 or s[0] == '0':
        return 0

    dp = [0] * (n + 1)

    dp[0] = 1
    dp[1] = 1

    for i in range(2, n + 1):
        current = s[i - 1]
        previous = s[i - 2]

        # One-digit decoding
        if current != '0':
            dp[i] += dp[i - 1]

        # Two-digit decoding
        number = (
            int(previous) * 10 + int(current)
        )

        if 10 <= number <= 26:
            dp[i] += dp[i - 2]

    return dp[n]
int decodeWays(string& s) {
    int n = s.size();

    if (n == 0 || s[0] == '0') {
        return 0;
    }

    vector<int> dp(n + 1);

    dp[0] = 1;
    dp[1] = 1;

    for (int i = 2; i <= n; i++) {

        char current = s[i - 1];
        char previous = s[i - 2];

        // One-digit decoding
        if (current != '0') {
            dp[i] += dp[i - 1];
        }

        // Two-digit decoding
        int number =
            (previous - '0') * 10
            + (current - '0');

        if (number >= 10 && number <= 26) {
            dp[i] += dp[i - 2];
        }
    }

    return dp[n];
}
function decodeWays(s) {
  const n = s.length;

  if (n === 0 || s[0] === '0') {
    return 0;
  }

  const dp = new Array(n + 1).fill(0);

  dp[0] = 1;
  dp[1] = 1;

  for (let i = 2; i <= n; i++) {
    const current = s[i - 1];
    const previous = s[i - 2];

    // One-digit decoding
    if (current !== '0') {
      dp[i] += dp[i - 1];
    }

    // Two-digit decoding
    const number = +previous * 10 + +current;

    if (number >= 10 && number <= 26) {
      dp[i] += dp[i - 2];
    }
  }

  return dp[n];
}

Mental Trigger

Numeric string + count valid interpretations → Decode DP

7. Wildcard Matching

Wildcard matching uses:

? → exactly one character
* → zero or more characters

This is a 2D pattern matching DP.

State

dp[i][j]
=
whether first i characters of string
match first j characters of pattern

Transition

If:

pattern[j-1] == '?'

or characters match:

dp[i][j] = dp[i-1][j-1]

For *:

dp[i][j]
=
dp[i][j-1]      // * matches empty

OR

dp[i-1][j]      // * matches one/more characters

Java Template

public static boolean wildcardMatch(String s, String p) {
    int n = s.length();
    int m = p.length();

    boolean[][] dp = new boolean[n + 1][m + 1];

    dp[0][0] = true;

    // Empty string vs pattern containing only *
    for (int j = 1; j <= m; j++) {
        if (p.charAt(j - 1) == '*') {
            dp[0][j] = dp[0][j - 1];
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {

            char pc = p.charAt(j - 1);

            if (pc == '*') {

                dp[i][j] =
                    dp[i][j - 1]
                    || dp[i - 1][j];

            } else if (
                pc == '?'
                || pc == s.charAt(i - 1)
            ) {

                dp[i][j] =
                    dp[i - 1][j - 1];
            }
        }
    }

    return dp[n][m];
}
def wildcard_match(s, p):
    n = len(s)
    m = len(p)

    dp = [[False] * (m + 1) for _ in range(n + 1)]

    dp[0][0] = True

    # Empty string vs pattern containing only *
    for j in range(1, m + 1):
        if p[j - 1] == '*':
            dp[0][j] = dp[0][j - 1]

    for i in range(1, n + 1):
        for j in range(1, m + 1):

            pc = p[j - 1]

            if pc == '*':
                dp[i][j] = (
                    dp[i][j - 1] or dp[i - 1][j]
                )

            elif pc == '?' or pc == s[i - 1]:
                dp[i][j] = dp[i - 1][j - 1]

    return dp[n][m]
bool wildcardMatch(string& s, string& p) {
    int n = s.size();
    int m = p.size();

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

    dp[0][0] = true;

    // Empty string vs pattern containing only *
    for (int j = 1; j <= m; j++) {
        if (p[j - 1] == '*') {
            dp[0][j] = dp[0][j - 1];
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {

            char pc = p[j - 1];

            if (pc == '*') {

                dp[i][j] =
                    dp[i][j - 1]
                    || dp[i - 1][j];

            } else if (
                pc == '?'
                || pc == s[i - 1]
            ) {

                dp[i][j] =
                    dp[i - 1][j - 1];
            }
        }
    }

    return dp[n][m];
}
function wildcardMatch(s, p) {
  const n = s.length;
  const m = p.length;

  const dp = Array.from({ length: n + 1 }, () =>
    new Array(m + 1).fill(false)
  );

  dp[0][0] = true;

  // Empty string vs pattern containing only *
  for (let j = 1; j <= m; j++) {
    if (p[j - 1] === '*') {
      dp[0][j] = dp[0][j - 1];
    }
  }

  for (let i = 1; i <= n; i++) {
    for (let j = 1; j <= m; j++) {
      const pc = p[j - 1];

      if (pc === '*') {
        dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
      } else if (pc === '?' || pc === s[i - 1]) {
        dp[i][j] = dp[i - 1][j - 1];
      }
    }
  }

  return dp[n][m];
}

Mental Trigger

Pattern contains ? and * → Wildcard DP

8. Regular Expression Matching

Regex matching looks similar to wildcard matching but the rules are different.

. → any single character

* → zero or more occurrences
     of the previous character

This distinction is extremely important.

Wildcard

* = any sequence of characters

Regex

a* = zero or more 'a's

Therefore, do not reuse the wildcard transition blindly.

State

dp[i][j]
=
whether first i characters of s
match first j characters of pattern

Java Template

public static boolean regexMatch(String s, String p) {
    int n = s.length();
    int m = p.length();

    boolean[][] dp = new boolean[n + 1][m + 1];

    dp[0][0] = true;

    // Patterns like a*, a*b*, a*b*c*
    for (int j = 2; j <= m; j++) {
        if (p.charAt(j - 1) == '*') {
            dp[0][j] = dp[0][j - 2];
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {

            char sc = s.charAt(i - 1);
            char pc = p.charAt(j - 1);

            if (pc == '.' || pc == sc) {

                dp[i][j] =
                    dp[i - 1][j - 1];

            } else if (pc == '*') {

                // Zero occurrences
                dp[i][j] =
                    dp[i][j - 2];

                char previous = p.charAt(j - 2);

                if (previous == '.' || previous == sc) {

                    // One or more occurrences
                    dp[i][j] =
                        dp[i][j]
                        || dp[i - 1][j];
                }
            }
        }
    }

    return dp[n][m];
}
def regex_match(s, p):
    n = len(s)
    m = len(p)

    dp = [[False] * (m + 1) for _ in range(n + 1)]

    dp[0][0] = True

    # Patterns like a*, a*b*, a*b*c*
    for j in range(2, m + 1):
        if p[j - 1] == '*':
            dp[0][j] = dp[0][j - 2]

    for i in range(1, n + 1):
        for j in range(1, m + 1):

            sc = s[i - 1]
            pc = p[j - 1]

            if pc == '.' or pc == sc:
                dp[i][j] = dp[i - 1][j - 1]

            elif pc == '*':
                # Zero occurrences
                dp[i][j] = dp[i][j - 2]

                previous = p[j - 2]

                if previous == '.' or previous == sc:
                    # One or more occurrences
                    dp[i][j] = (
                        dp[i][j] or dp[i - 1][j]
                    )

    return dp[n][m]
bool regexMatch(string& s, string& p) {
    int n = s.size();
    int m = p.size();

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

    dp[0][0] = true;

    // Patterns like a*, a*b*, a*b*c*
    for (int j = 2; j <= m; j++) {
        if (p[j - 1] == '*') {
            dp[0][j] = dp[0][j - 2];
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {

            char sc = s[i - 1];
            char pc = p[j - 1];

            if (pc == '.' || pc == sc) {

                dp[i][j] =
                    dp[i - 1][j - 1];

            } else if (pc == '*') {

                // Zero occurrences
                dp[i][j] =
                    dp[i][j - 2];

                char previous = p[j - 2];

                if (previous == '.' || previous == sc) {

                    // One or more occurrences
                    dp[i][j] =
                        dp[i][j]
                        || dp[i - 1][j];
                }
            }
        }
    }

    return dp[n][m];
}
function regexMatch(s, p) {
  const n = s.length;
  const m = p.length;

  const dp = Array.from({ length: n + 1 }, () =>
    new Array(m + 1).fill(false)
  );

  dp[0][0] = true;

  // Patterns like a*, a*b*, a*b*c*
  for (let j = 2; j <= m; j++) {
    if (p[j - 1] === '*') {
      dp[0][j] = dp[0][j - 2];
    }
  }

  for (let i = 1; i <= n; i++) {
    for (let j = 1; j <= m; j++) {
      const sc = s[i - 1];
      const pc = p[j - 1];

      if (pc === '.' || pc === sc) {
        dp[i][j] = dp[i - 1][j - 1];
      } else if (pc === '*') {
        // Zero occurrences
        dp[i][j] = dp[i][j - 2];

        const previous = p[j - 2];

        if (previous === '.' || previous === sc) {
          // One or more occurrences
          dp[i][j] = dp[i][j] || dp[i - 1][j];
        }
      }
    }
  }

  return dp[n][m];
}

Mental Trigger

. + * where * modifies previous character → Regex DP

9. Shortest Common Supersequence

A supersequence contains both strings as subsequences.

The key observation:

SCS can be built using the LCS structure.

If characters match, include one character.

If they differ, choose the shorter path.

State

dp[i][j]
=
length of shortest common supersequence
of first i characters of s1
and first j characters of s2

Java Template

public static int shortestCommonSupersequenceLength(
        String s1, String s2) {

    int n = s1.length();
    int m = s2.length();

    int[][] dp = new int[n + 1][m + 1];

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

    for (int j = 0; j <= m; j++) {
        dp[0][j] = j;
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {

            if (s1.charAt(i - 1) == s2.charAt(j - 1)) {

                dp[i][j] =
                    1 + dp[i - 1][j - 1];

            } else {

                dp[i][j] =
                    1 + Math.min(
                        dp[i - 1][j],
                        dp[i][j - 1]
                    );
            }
        }
    }

    return dp[n][m];
}
def shortest_common_supersequence_length(s1, s2):
    n = len(s1)
    m = len(s2)

    dp = [[0] * (m + 1) for _ in range(n + 1)]

    for i in range(n + 1):
        dp[i][0] = i

    for j in range(m + 1):
        dp[0][j] = j

    for i in range(1, n + 1):
        for j in range(1, m + 1):

            if s1[i - 1] == s2[j - 1]:
                dp[i][j] = 1 + dp[i - 1][j - 1]

            else:
                dp[i][j] = 1 + min(
                    dp[i - 1][j],
                    dp[i][j - 1]
                )

    return dp[n][m]
int shortestCommonSupersequenceLength(string& s1, string& s2) {
    int n = s1.size();
    int m = s2.size();

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

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

    for (int j = 0; j <= m; j++) {
        dp[0][j] = j;
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {

            if (s1[i - 1] == s2[j - 1]) {

                dp[i][j] =
                    1 + dp[i - 1][j - 1];

            } else {

                dp[i][j] =
                    1 + min(
                        dp[i - 1][j],
                        dp[i][j - 1]
                    );
            }
        }
    }

    return dp[n][m];
}
function shortestCommonSupersequenceLength(s1, s2) {
  const n = s1.length;
  const m = s2.length;

  const dp = Array.from({ length: n + 1 }, () =>
    new Array(m + 1).fill(0)
  );

  for (let i = 0; i <= n; i++) {
    dp[i][0] = i;
  }

  for (let j = 0; j <= m; j++) {
    dp[0][j] = j;
  }

  for (let i = 1; i <= n; i++) {
    for (let j = 1; j <= m; j++) {
      if (s1[i - 1] === s2[j - 1]) {
        dp[i][j] = 1 + dp[i - 1][j - 1];
      } else {
        dp[i][j] =
          1 +
          Math.min(dp[i - 1][j], dp[i][j - 1]);
      }
    }
  }

  return dp[n][m];
}

Important Formula

If only the length is required:

SCS length
=
n + m - LCS length

Mental Trigger

Merge two strings while preserving both → SCS / LCS extension

10. Interleaving String

Question:

Can s1 and s2 be interleaved to form s3?

Characters from each source string must remain in their original order.

State

dp[i][j]
=
whether first i characters of s1
and first j characters of s2
can form first i+j characters of s3

Java Template

public static boolean isInterleave(
        String s1,
        String s2,
        String s3) {

    int n = s1.length();
    int m = s2.length();

    if (n + m != s3.length()) {
        return false;
    }

    boolean[][] dp = new boolean[n + 1][m + 1];

    dp[0][0] = true;

    for (int i = 1; i <= n; i++) {
        dp[i][0] =
            dp[i - 1][0]
            && s1.charAt(i - 1) == s3.charAt(i - 1);
    }

    for (int j = 1; j <= m; j++) {
        dp[0][j] =
            dp[0][j - 1]
            && s2.charAt(j - 1) == s3.charAt(j - 1);
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {

            char target =
                s3.charAt(i + j - 1);

            boolean fromS1 =
                dp[i - 1][j]
                && s1.charAt(i - 1) == target;

            boolean fromS2 =
                dp[i][j - 1]
                && s2.charAt(j - 1) == target;

            dp[i][j] =
                fromS1 || fromS2;
        }
    }

    return dp[n][m];
}
def is_interleave(s1, s2, s3):
    n = len(s1)
    m = len(s2)

    if n + m != len(s3):
        return False

    dp = [[False] * (m + 1) for _ in range(n + 1)]

    dp[0][0] = True

    for i in range(1, n + 1):
        dp[i][0] = (
            dp[i - 1][0] and s1[i - 1] == s3[i - 1]
        )

    for j in range(1, m + 1):
        dp[0][j] = (
            dp[0][j - 1] and s2[j - 1] == s3[j - 1]
        )

    for i in range(1, n + 1):
        for j in range(1, m + 1):

            target = s3[i + j - 1]

            from_s1 = (
                dp[i - 1][j] and s1[i - 1] == target
            )

            from_s2 = (
                dp[i][j - 1] and s2[j - 1] == target
            )

            dp[i][j] = from_s1 or from_s2

    return dp[n][m]
bool isInterleave(string& s1, string& s2, string& s3) {
    int n = s1.size();
    int m = s2.size();

    if (n + m != (int)s3.size()) {
        return false;
    }

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

    dp[0][0] = true;

    for (int i = 1; i <= n; i++) {
        dp[i][0] =
            dp[i - 1][0]
            && s1[i - 1] == s3[i - 1];
    }

    for (int j = 1; j <= m; j++) {
        dp[0][j] =
            dp[0][j - 1]
            && s2[j - 1] == s3[j - 1];
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {

            char target =
                s3[i + j - 1];

            bool fromS1 =
                dp[i - 1][j]
                && s1[i - 1] == target;

            bool fromS2 =
                dp[i][j - 1]
                && s2[j - 1] == target;

            dp[i][j] =
                fromS1 || fromS2;
        }
    }

    return dp[n][m];
}
function isInterleave(s1, s2, s3) {
  const n = s1.length;
  const m = s2.length;

  if (n + m !== s3.length) {
    return false;
  }

  const dp = Array.from({ length: n + 1 }, () =>
    new Array(m + 1).fill(false)
  );

  dp[0][0] = true;

  for (let i = 1; i <= n; i++) {
    dp[i][0] =
      dp[i - 1][0] && s1[i - 1] === s3[i - 1];
  }

  for (let j = 1; j <= m; j++) {
    dp[0][j] =
      dp[0][j - 1] && s2[j - 1] === s3[j - 1];
  }

  for (let i = 1; i <= n; i++) {
    for (let j = 1; j <= m; j++) {
      const target = s3[i + j - 1];

      const fromS1 =
        dp[i - 1][j] && s1[i - 1] === target;

      const fromS2 =
        dp[i][j - 1] && s2[j - 1] === target;

      dp[i][j] = fromS1 || fromS2;
    }
  }

  return dp[n][m];
}

Mental Trigger

Two strings → form a third while preserving order → Interleaving DP

11. Word Break

Word Break is usually 1D Prefix DP, not traditional 2D String DP.

Question:

Can the string be divided into valid dictionary words?

State

dp[i]
=
whether first i characters
can be segmented

For every ending position, try a previous split.

Java Template

public static boolean wordBreak(
        String s,
        Set<String> dictionary) {

    int n = s.length();

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

    dp[0] = true;

    for (int i = 1; i <= n; i++) {

        for (int j = 0; j < i; j++) {

            if (dp[j]
                    && dictionary.contains(
                        s.substring(j, i)
                    )) {

                dp[i] = true;
                break;
            }
        }
    }

    return dp[n];
}
def word_break(s, dictionary):
    n = len(s)

    dp = [False] * (n + 1)

    dp[0] = True

    for i in range(1, n + 1):

        for j in range(i):

            if dp[j] and s[j:i] in dictionary:
                dp[i] = True
                break

    return dp[n]
bool wordBreak(string& s, unordered_set<string>& dictionary) {
    int n = s.size();

    vector<bool> dp(n + 1, false);

    dp[0] = true;

    for (int i = 1; i <= n; i++) {

        for (int j = 0; j < i; j++) {

            if (dp[j]
                    && dictionary.count(
                        s.substr(j, i - j)
                    )) {

                dp[i] = true;
                break;
            }
        }
    }

    return dp[n];
}
function wordBreak(s, dictionary) {
  const n = s.length;

  const dp = new Array(n + 1).fill(false);

  dp[0] = true;

  for (let i = 1; i <= n; i++) {
    for (let j = 0; j < i; j++) {
      if (dp[j] && dictionary.has(s.slice(j, i))) {
        dp[i] = true;
        break;
      }
    }
  }

  return dp[n];
}

Mental Trigger

String + dictionary + segmentation → Prefix DP

12. Palindrome Partitioning

This is where String DP and Interval/Partition DP overlap.

Question:

What is the minimum number of cuts needed to divide a string into palindromes?

There are two states:

palindrome[i][j]
=
is s[i...j] a palindrome?

cuts[i]
=
minimum cuts for s[0...i-1]

Java Template

public static int minPalindromeCuts(String s) {
    int n = s.length();

    boolean[][] palindrome =
        new boolean[n][n];

    // Build palindrome table
    for (int i = n - 1; i >= 0; i--) {

        for (int j = i; j < n; j++) {

            if (s.charAt(i) == s.charAt(j)
                    && (j - i <= 2
                    || palindrome[i + 1][j - 1])) {

                palindrome[i][j] = true;
            }
        }
    }

    int[] cuts = new int[n + 1];

    cuts[0] = -1;

    for (int i = 1; i <= n; i++) {

        cuts[i] = Integer.MAX_VALUE;

        for (int j = 0; j < i; j++) {

            if (palindrome[j][i - 1]) {

                cuts[i] =
                    Math.min(
                        cuts[i],
                        cuts[j] + 1
                    );
            }
        }
    }

    return cuts[n];
}
def min_palindrome_cuts(s):
    n = len(s)

    palindrome = [[False] * n for _ in range(n)]

    # Build palindrome table
    for i in range(n - 1, -1, -1):

        for j in range(i, n):

            if s[i] == s[j] and (
                j - i <= 2 or palindrome[i + 1][j - 1]
            ):
                palindrome[i][j] = True

    cuts = [0] * (n + 1)

    cuts[0] = -1

    for i in range(1, n + 1):
        cuts[i] = float('inf')

        for j in range(i):
            if palindrome[j][i - 1]:
                cuts[i] = min(cuts[i], cuts[j] + 1)

    return cuts[n]
int minPalindromeCuts(string& s) {
    int n = s.size();

    vector<vector<bool>> palindrome(
        n, vector<bool>(n));

    // Build palindrome table
    for (int i = n - 1; i >= 0; i--) {

        for (int j = i; j < n; j++) {

            if (s[i] == s[j]
                    && (j - i <= 2
                    || palindrome[i + 1][j - 1])) {

                palindrome[i][j] = true;
            }
        }
    }

    vector<int> cuts(n + 1);

    cuts[0] = -1;

    for (int i = 1; i <= n; i++) {

        cuts[i] = INT_MAX;

        for (int j = 0; j < i; j++) {

            if (palindrome[j][i - 1]) {

                cuts[i] =
                    min(
                        cuts[i],
                        cuts[j] + 1
                    );
            }
        }
    }

    return cuts[n];
}
function minPalindromeCuts(s) {
  const n = s.length;

  const palindrome = Array.from({ length: n }, () =>
    new Array(n).fill(false)
  );

  // Build palindrome table
  for (let i = n - 1; i >= 0; i--) {
    for (let j = i; j < n; j++) {
      if (
        s[i] === s[j] &&
        (j - i <= 2 || palindrome[i + 1][j - 1])
      ) {
        palindrome[i][j] = true;
      }
    }
  }

  const cuts = new Array(n + 1);

  cuts[0] = -1;

  for (let i = 1; i <= n; i++) {
    cuts[i] = Infinity;

    for (let j = 0; j < i; j++) {
      if (palindrome[j][i - 1]) {
        cuts[i] = Math.min(cuts[i], cuts[j] + 1);
      }
    }
  }

  return cuts[n];
}

Mental Trigger

Palindrome + partition/cuts → Palindrome + Partition DP

Generic String DP Templates

There is no single String DP template that correctly solves every problem.

Instead, use the template according to the relationship between the strings.

Template A — Two-String Prefix DP

Use when:

dp[i][j]

depends on prefixes of two strings.

Typical problems:

LCS
Edit Distance
Distinct Subsequences
SCS
Interleaving
Wildcard Matching
Regex Matching

Generic structure:

for (int i = 1; i <= n; i++) {

    for (int j = 1; j <= m; j++) {

        if (condition) {

            dp[i][j] = ...;

        } else {

            dp[i][j] = ...;
        }
    }
}
for i in range(1, n + 1):

    for j in range(1, m + 1):

        if condition:

            dp[i][j] = ...

        else:

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

    for (int j = 1; j <= m; j++) {

        if (condition) {

            dp[i][j] = ...;

        } else {

            dp[i][j] = ...;
        }
    }
}
for (let i = 1; i <= n; i++) {
  for (let j = 1; j <= m; j++) {
    if (condition) {
      dp[i][j] = ...;
    } else {
      dp[i][j] = ...;
    }
  }
}

Template B — Substring / Interval DP

Use when the state represents:

s[i...j]

Typical problems:

Palindrome DP
Longest Palindromic Substring
Palindrome Partitioning
Interval String Problems

Generic structure:

for (int i = n - 1; i >= 0; i--) {

    for (int j = i; j < n; j++) {

        if (condition involving i and j) {

            dp[i][j] = ...;

        }
    }
}
for i in range(n - 1, -1, -1):

    for j in range(i, n):

        if condition_involving_i_and_j:

            dp[i][j] = ...
for (int i = n - 1; i >= 0; i--) {

    for (int j = i; j < n; j++) {

        if (condition involving i and j) {

            dp[i][j] = ...;

        }
    }
}
for (let i = n - 1; i >= 0; i--) {
  for (let j = i; j < n; j++) {
    if (condition involving i and j) {
      dp[i][j] = ...;
    }
  }
}

The reverse i iteration is important when:

dp[i][j]
depends on
dp[i+1][j-1]

Template C — Prefix DP

Use when the answer depends on how a string can be constructed up to position i.

Typical problems:

Word Break
Decode Ways
String segmentation
Prefix construction

Generic structure:

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

dp[0] = true;

for (int i = 1; i <= n; i++) {

    for (int j = 0; j < i; j++) {

        if (dp[j] && valid(j, i)) {
            dp[i] = true;
            break;
        }
    }
}
dp = [False] * (n + 1)

dp[0] = True

for i in range(1, n + 1):

    for j in range(i):

        if dp[j] and valid(j, i):
            dp[i] = True
            break
vector<bool> dp(n + 1, false);

dp[0] = true;

for (int i = 1; i <= n; i++) {

    for (int j = 0; j < i; j++) {

        if (dp[j] && valid(j, i)) {
            dp[i] = true;
            break;
        }
    }
}
const dp = new Array(n + 1).fill(false);

dp[0] = true;

for (let i = 1; i <= n; i++) {
  for (let j = 0; j < i; j++) {
    if (dp[j] && valid(j, i)) {
      dp[i] = true;
      break;
    }
  }
}

For counting problems:

long[] dp = new long[n + 1];

dp[0] = 1;

for (int i = 1; i <= n; i++) {

    for (int j = 0; j < i; j++) {

        if (valid(j, i)) {
            dp[i] += dp[j];
        }
    }
}
dp = [0] * (n + 1)

dp[0] = 1

for i in range(1, n + 1):

    for j in range(i):

        if valid(j, i):
            dp[i] += dp[j]
vector<long long> dp(n + 1, 0);

dp[0] = 1;

for (int i = 1; i <= n; i++) {

    for (int j = 0; j < i; j++) {

        if (valid(j, i)) {
            dp[i] += dp[j];
        }
    }
}
const dp = new Array(n + 1).fill(0);

dp[0] = 1;

for (let i = 1; i <= n; i++) {
  for (let j = 0; j < i; j++) {
    if (valid(j, i)) {
      dp[i] += dp[j];
    }
  }
}

Template D — Palindrome DP

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

for (int i = n - 1; i >= 0; i--) {

    for (int j = i; j < n; j++) {

        if (s.charAt(i) == s.charAt(j)
                && (j - i <= 2
                || dp[i + 1][j - 1])) {

            dp[i][j] = true;
        }
    }
}
dp = [[False] * n for _ in range(n)]

for i in range(n - 1, -1, -1):

    for j in range(i, n):

        if s[i] == s[j] and (
            j - i <= 2 or dp[i + 1][j - 1]
        ):
            dp[i][j] = True
vector<vector<bool>> dp(n, vector<bool>(n));

for (int i = n - 1; i >= 0; i--) {

    for (int j = i; j < n; j++) {

        if (s[i] == s[j]
                && (j - i <= 2
                || dp[i + 1][j - 1])) {

            dp[i][j] = true;
        }
    }
}
const dp = Array.from({ length: n }, () =>
  new Array(n).fill(false)
);

for (let i = n - 1; i >= 0; i--) {
  for (let j = i; j < n; j++) {
    if (
      s[i] === s[j] &&
      (j - i <= 2 || dp[i + 1][j - 1])
    ) {
      dp[i][j] = true;
    }
  }
}

Use this whenever the problem asks about:

palindrome
symmetric substring
palindromic range

Most Important Differences

LCS vs Longest Common Substring

LCS:

match
    ↓
diagonal + 1

mismatch
    ↓
max(top, left)
Substring:

match
    ↓
diagonal + 1

mismatch
    ↓
0

Remember

LCS can skip. Substring cannot.

LCS vs Edit Distance

LCSEdit Distance
OptimizationMinimization
Find common sequenceTransform strings
Skip charactersInsert/Delete/Replace
Match → diagonalMatch → diagonal
Mismatch → maxMismatch → 1 + min(...)

Trigger:

"common" → LCS

"convert" → Edit Distance

Wildcard vs Regex

This is a very common exam trap.

Wildcard

? → one character

* → any number of characters

Example:

a*b

* can match:

""
"a"
"abc"
"aaaa"

Regex

. → one character

* → repeat previous character

Example:

a*

matches:

""
"a"
"aa"
"aaa"

but not:

"b"
"ab"

Remember

Wildcard * represents characters. Regex * repeats the previous pattern.

Palindrome DP vs LCS

They can both use 2D arrays, but their states are completely different.

LCS

dp[i][j]

Two strings
    ↓
prefix i vs prefix j

Palindrome

dp[i][j]

One string
    ↓
range [i...j]

Remember:

Two strings → usually prefix comparison.

One string + [i...j] → usually interval/string DP.

Word Break vs Palindrome Partitioning

Both split strings, but the validity condition is different.

Word Break

Is s[j...i] in dictionary?

Palindrome Partitioning

Is s[j...i] a palindrome?

So:

Dictionary segmentation
        ↓
Prefix DP

Palindrome segmentation
        ↓
Palindrome + Partition DP

Complexity Cheat Sheet

PatternTimeSpace
LCSO(nm)O(nm)
LCS optimizedO(nm)O(m)
Longest Common SubstringO(nm)O(nm)
Edit DistanceO(nm)O(nm)
Distinct SubsequencesO(nm)O(nm)
Palindrome TableO(n²)O(n²)
Decode WaysO(n)O(n)
Wildcard MatchingO(nm)O(nm)
Regex MatchingO(nm)O(nm)
SCS LengthO(nm)O(nm)
Interleaving StringO(nm)O(nm)
Word BreakO(n²) + dictionary lookupO(n)
Palindrome PartitioningO(n²)O(n²)

String DP Recognition Cheat Sheet

If you see…Think…
Two strings + common subsequenceLCS
Two strings + continuous matchLongest Common Substring
Insert/Delete/ReplaceEdit Distance
Count subsequences forming targetDistinct Subsequences
Palindrome/symmetryPalindrome DP
Numeric string + decodingDecode Ways
? and *Wildcard DP
. and *Regex DP
Merge two stringsShortest Common Supersequence
Two strings form a thirdInterleaving DP
Dictionary + segmentationWord Break / Prefix DP
Palindrome + minimum cutsPalindrome Partition DP

How to Identify String DP

Before coding, ask:

1. How many strings are involved?

One string
    ↓
Palindrome / Prefix / Partition DP

Two strings
    ↓
LCS / Edit Distance / Matching DP

Three strings
    ↓
Interleaving-style DP

2. What does the question want?

Longest
    ↓
Optimization DP

Minimum
    ↓
Min DP

Number of ways
    ↓
Counting DP

Can it be done?
    ↓
Boolean DP

3. Are characters allowed to be skipped?

Yes
    ↓
Subsequence

No
    ↓
Substring

4. Is the state a prefix or a range?

first i characters
    ↓
Prefix DP

first i + first j
    ↓
Two-string DP

s[i...j]
    ↓
Interval / Palindrome DP

My Private Notes

Notes are auto-saved locally to this device.