Longest Palindromic Subsequence

🎯

Longest Palindromic Subsequence

mediumDPAmazonGoogle

Imagine you want to find the longest sequence of characters in a string that reads the same forwards and backwards, like a secret code hidden inside a message.

💡 This problem is a classic example of dynamic programming on strings. Beginners often struggle because palindromes involve symmetry and subsequences allow skipping characters, making brute force solutions inefficient and hard to optimize without DP.

📋

Problem Statement

Given a string s, find the length of the longest palindromic subsequence in s. A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.

1 ≤ length of s ≤ 10^5s consists only of lowercase English letters

💡

Example

Input"bbbab"

Output4

One longest palindromic subsequence is 'bbbb'.

Input"cbbd"

Output2

One longest palindromic subsequence is 'bb'.

• Empty string → 0
• String with all identical characters → length of string
• String with no repeating characters → 1
• String of length 1 → 1

🔁

Why DP?

Why greedy fails:

A greedy approach might try to match characters from the ends inward, but this fails when the best palindrome skips some characters. For example, in 'agbdba', greedily matching 'a' at both ends misses the longer palindrome 'abdba'.

DP state:

dp[i][j] represents the length of the longest palindromic subsequence in the substring s[i..j].

Recurrence:dp[i][j] = dp[i+1][j-1] + 2 if s[i] == s[j] else max(dp[i+1][j], dp[i][j-1])

If the characters at i and j match, add 2 to the result from the substring inside; otherwise, take the max excluding one character from either end.

⚠️

Common Mistakes

Not handling base case i > j correctly

Incorrect results or infinite recursion

✅ Add explicit base case returning 0 when i > j

Confusing substring indices leading to out-of-bound errors

Runtime errors or wrong answers

✅ Carefully check loop bounds and conditions for i and j

Forgetting to initialize dp[i][i] = 1 in tabulation

Palindromes of length 1 not counted, wrong results

✅ Initialize all single character substrings as palindrome length 1

Overwriting dp values too early in space optimized approach

Incorrect dp results due to lost dependencies

✅ Iterate start index backwards and use temporary variables to preserve values

Using greedy approach to match ends without recursion or DP

Misses longer palindromic subsequences, incorrect answers

✅ Use DP to consider all subsequences, not just greedy matches

🧠

Brute Force (Pure Recursion)

💡 Starting with brute force helps understand the problem's recursive structure and why naive solutions are inefficient due to repeated computations.

Intuition

Try all subsequences by recursively checking characters from both ends, and combine results based on whether characters match or not.

Algorithm

1. If the substring length is 1, return 1 (single character palindrome).
2. If the substring length is 0, return 0 (empty substring).
3. If characters at start and end match, add 2 plus result of inner substring.
4. Otherwise, return max of results excluding one character from either end.

💡 The recursion is simple but leads to exponential calls because it recomputes many overlapping substrings.

Recurrence:lps(i, j) = 1 if i == j; 0 if i > j; else if s[i] == s[j] then 2 + lps(i+1, j-1) else max(lps(i+1, j), lps(i, j-1))

</>

Code

def lps(s, i, j):
    if i > j:
        return 0
    if i == j:
        return 1
    if s[i] == s[j]:
        return 2 + lps(s, i+1, j-1)
    else:
        return max(lps(s, i+1, j), lps(s, i, j-1))

if __name__ == '__main__':
    s = 'bbbab'
    print(lps(s, 0, len(s)-1))

Line Notes

if i > j:Base case: empty substring has length 0

if i == j:Base case: single character is palindrome length 1

if s[i] == s[j]:If ends match, include both and recurse inside

return max(lps(s, i+1, j), lps(s, i, j-1))If no match, try skipping one end to find max palindrome

public class Solution {
    public static int lps(String s, int i, int j) {
        if (i > j) return 0;
        if (i == j) return 1;
        if (s.charAt(i) == s.charAt(j)) {
            return 2 + lps(s, i+1, j-1);
        } else {
            return Math.max(lps(s, i+1, j), lps(s, i, j-1));
        }
    }
    public static void main(String[] args) {
        String s = "bbbab";
        System.out.println(lps(s, 0, s.length()-1));
    }
}

Line Notes

if (i > j) return 0;Empty substring base case

if (i == j) return 1;Single character palindrome base case

if (s.charAt(i) == s.charAt(j)) {Matching ends add 2 plus inner result

return Math.max(lps(s, i+1, j), lps(s, i, j-1));Try skipping one end if no match

#include <iostream>
#include <string>
using namespace std;

int lps(const string &s, int i, int j) {
    if (i > j) return 0;
    if (i == j) return 1;
    if (s[i] == s[j]) {
        return 2 + lps(s, i+1, j-1);
    } else {
        return max(lps(s, i+1, j), lps(s, i, j-1));
    }
}

int main() {
    string s = "bbbab";
    cout << lps(s, 0, s.size()-1) << endl;
    return 0;
}

Line Notes

if (i > j) return 0;Empty substring base case

if (i == j) return 1;Single character palindrome base case

if (s[i] == s[j]) {Matching ends add 2 plus inner substring result

return max(lps(s, i+1, j), lps(s, i, j-1));Try skipping one end if no match

function lps(s, i, j) {
    if (i > j) return 0;
    if (i === j) return 1;
    if (s[i] === s[j]) {
        return 2 + lps(s, i+1, j-1);
    } else {
        return Math.max(lps(s, i+1, j), lps(s, i, j-1));
    }
}

const s = 'bbbab';
console.log(lps(s, 0, s.length - 1));

Line Notes

if (i > j) return 0;Empty substring base case

if (i === j) return 1;Single character palindrome base case

if (s[i] === s[j]) {Matching ends add 2 plus inner substring result

return Math.max(lps(s, i+1, j), lps(s, i, j-1));Try skipping one end if no match

⏱

Complexity

TimeO(2^n)

SpaceO(n) recursion stack

Each call branches into two calls except base cases, leading to exponential growth.

💡 For n=20, this means over a million calls, which is impractical.

Interview Verdict: TLE

This approach is too slow for large inputs but is essential to understand the problem's recursive nature.

🧠

Top-Down Memoization

💡 Memoization caches results of recursive calls to avoid recomputation, drastically improving efficiency while preserving the recursive intuition.

Intuition

Store results of lps(i, j) in a table so repeated calls return instantly instead of recomputing.

Algorithm

1. Initialize a 2D memo table with -1 indicating uncomputed states.
2. Recursively compute lps(i, j) using the same logic as brute force.
3. Before computing, check if memo[i][j] is already computed and return it if so.
4. Store computed results in memo to reuse.

💡 Memoization avoids exponential recomputation by remembering results, turning recursion into efficient DP.

Recurrence:Same as brute force: lps(i, j) = 1 if i == j; 0 if i > j; else if s[i] == s[j] then 2 + lps(i+1, j-1) else max(lps(i+1, j), lps(i, j-1))

</>

Code

def lps(s, i, j, memo):
    if i > j:
        return 0
    if i == j:
        return 1
    if memo[i][j] != -1:
        return memo[i][j]
    if s[i] == s[j]:
        memo[i][j] = 2 + lps(s, i+1, j-1, memo)
    else:
        memo[i][j] = max(lps(s, i+1, j, memo), lps(s, i, j-1, memo))
    return memo[i][j]

if __name__ == '__main__':
    s = 'bbbab'
    n = len(s)
    memo = [[-1]*n for _ in range(n)]
    print(lps(s, 0, n-1, memo))

Line Notes

if memo[i][j] != -1:Return cached result to avoid recomputation

memo[i][j] = 2 + lps(s, i+1, j-1, memo)Store result when ends match

memo[i][j] = max(lps(s, i+1, j, memo), lps(s, i, j-1, memo))Store max result when ends differ

memo = [[-1]*n for _ in range(n)]Initialize memo table with -1 to mark uncomputed

public class Solution {
    public static int lps(String s, int i, int j, int[][] memo) {
        if (i > j) return 0;
        if (i == j) return 1;
        if (memo[i][j] != -1) return memo[i][j];
        if (s.charAt(i) == s.charAt(j)) {
            memo[i][j] = 2 + lps(s, i+1, j-1, memo);
        } else {
            memo[i][j] = Math.max(lps(s, i+1, j, memo), lps(s, i, j-1, memo));
        }
        return memo[i][j];
    }
    public static void main(String[] args) {
        String s = "bbbab";
        int n = s.length();
        int[][] memo = new int[n][n];
        for (int[] row : memo) java.util.Arrays.fill(row, -1);
        System.out.println(lps(s, 0, n-1, memo));
    }
}

Line Notes

if (memo[i][j] != -1) return memo[i][j];Return cached result to avoid recomputation

memo[i][j] = 2 + lps(s, i+1, j-1, memo);Store result when ends match

memo[i][j] = Math.max(lps(s, i+1, j, memo), lps(s, i, j-1, memo));Store max result when ends differ

for (int[] row : memo) java.util.Arrays.fill(row, -1);Initialize memo table with -1

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int lps(const string &s, int i, int j, vector<vector<int>> &memo) {
    if (i > j) return 0;
    if (i == j) return 1;
    if (memo[i][j] != -1) return memo[i][j];
    if (s[i] == s[j]) {
        memo[i][j] = 2 + lps(s, i+1, j-1, memo);
    } else {
        memo[i][j] = max(lps(s, i+1, j, memo), lps(s, i, j-1, memo));
    }
    return memo[i][j];
}

int main() {
    string s = "bbbab";
    int n = s.size();
    vector<vector<int>> memo(n, vector<int>(n, -1));
    cout << lps(s, 0, n-1, memo) << endl;
    return 0;
}

Line Notes

if (memo[i][j] != -1) return memo[i][j];Return cached result to avoid recomputation

memo[i][j] = 2 + lps(s, i+1, j-1, memo);Store result when ends match

memo[i][j] = max(lps(s, i+1, j, memo), lps(s, i, j-1, memo));Store max result when ends differ

vector<vector<int>> memo(n, vector<int>(n, -1));Initialize memo table with -1

function lps(s, i, j, memo) {
    if (i > j) return 0;
    if (i === j) return 1;
    if (memo[i][j] !== -1) return memo[i][j];
    if (s[i] === s[j]) {
        memo[i][j] = 2 + lps(s, i+1, j-1, memo);
    } else {
        memo[i][j] = Math.max(lps(s, i+1, j, memo), lps(s, i, j-1, memo));
    }
    return memo[i][j];
}

const s = 'bbbab';
const n = s.length;
const memo = Array.from({length: n}, () => Array(n).fill(-1));
console.log(lps(s, 0, n-1, memo));

Line Notes

if (memo[i][j] !== -1) return memo[i][j];Return cached result to avoid recomputation

memo[i][j] = 2 + lps(s, i+1, j-1, memo);Store result when ends match

memo[i][j] = Math.max(lps(s, i+1, j, memo), lps(s, i, j-1, memo));Store max result when ends differ

const memo = Array.from({length: n}, () => Array(n).fill(-1));Initialize memo table with -1

⏱

Complexity

TimeO(n^2)

SpaceO(n^2) for memo + O(n) recursion stack

Each substring state is computed once and stored, reducing exponential calls to polynomial.

💡 For n=1000, this means about 1 million states, which is feasible with memoization.

Interview Verdict: Accepted

Memoization makes the solution efficient enough for typical interview constraints.

🧠

Bottom-Up Tabulation

💡 Tabulation builds the solution iteratively from smaller substrings to larger ones, eliminating recursion and making the process explicit.

Intuition

Fill a 2D dp table where dp[i][j] stores the longest palindromic subsequence length for substring s[i..j], starting from substrings of length 1 up to n.

Algorithm

1. Initialize dp[i][i] = 1 for all i (single characters).
2. Iterate over substring lengths from 2 to n.
3. For each substring s[i..j], if s[i] == s[j], dp[i][j] = 2 + dp[i+1][j-1].
4. Otherwise, dp[i][j] = max(dp[i+1][j], dp[i][j-1]).
5. Return dp[0][n-1] as the answer.

💡 This approach ensures all dependencies are computed before use, making it efficient and easy to debug.

Recurrence:dp[i][j] = dp[i+1][j-1] + 2 if s[i] == s[j] else max(dp[i+1][j], dp[i][j-1])

</>

Code

def longest_palindromic_subsequence(s):
    n = len(s)
    dp = [[0]*n for _ in range(n)]
    for i in range(n):
        dp[i][i] = 1
    for length in range(2, n+1):
        for i in range(n-length+1):
            j = i + length - 1
            if s[i] == s[j]:
                dp[i][j] = 2 + (dp[i+1][j-1] if i+1 <= j-1 else 0)
            else:
                dp[i][j] = max(dp[i+1][j], dp[i][j-1])
    return dp[0][n-1]

if __name__ == '__main__':
    print(longest_palindromic_subsequence('bbbab'))

Line Notes

dp = [[0]*n for _ in range(n)]Create 2D dp table initialized to 0

dp[i][i] = 1Single characters are palindromes of length 1

for length in range(2, n+1):Iterate over substring lengths from 2 to n

if s[i] == s[j]:If ends match, add 2 plus inner substring result

public class Solution {
    public static int longestPalindromicSubsequence(String s) {
        int n = s.length();
        int[][] dp = new int[n][n];
        for (int i = 0; i < n; i++) dp[i][i] = 1;
        for (int length = 2; length <= n; length++) {
            for (int i = 0; i <= n - length; i++) {
                int j = i + length - 1;
                if (s.charAt(i) == s.charAt(j)) {
                    dp[i][j] = 2 + (i+1 <= j-1 ? dp[i+1][j-1] : 0);
                } else {
                    dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]);
                }
            }
        }
        return dp[0][n-1];
    }
    public static void main(String[] args) {
        System.out.println(longestPalindromicSubsequence("bbbab"));
    }
}

Line Notes

int[][] dp = new int[n][n];Initialize 2D dp array

dp[i][i] = 1;Single characters are palindromes

for (int length = 2; length <= n; length++) {Loop over substring lengths

if (s.charAt(i) == s.charAt(j)) {Matching ends add 2 plus inner substring

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int longestPalindromicSubsequence(const string &s) {
    int n = s.size();
    vector<vector<int>> dp(n, vector<int>(n, 0));
    for (int i = 0; i < n; i++) dp[i][i] = 1;
    for (int length = 2; length <= n; length++) {
        for (int i = 0; i <= n - length; i++) {
            int j = i + length - 1;
            if (s[i] == s[j]) {
                dp[i][j] = 2 + (i+1 <= j-1 ? dp[i+1][j-1] : 0);
            } else {
                dp[i][j] = max(dp[i+1][j], dp[i][j-1]);
            }
        }
    }
    return dp[0][n-1];
}

int main() {
    cout << longestPalindromicSubsequence("bbbab") << endl;
    return 0;
}

Line Notes

vector<vector<int>> dp(n, vector<int>(n, 0));Initialize 2D dp vector

dp[i][i] = 1;Single characters are palindromes

for (int length = 2; length <= n; length++) {Loop over substring lengths

if (s[i] == s[j]) {Matching ends add 2 plus inner substring

function longestPalindromicSubsequence(s) {
    const n = s.length;
    const dp = Array.from({length: n}, () => Array(n).fill(0));
    for (let i = 0; i < n; i++) dp[i][i] = 1;
    for (let length = 2; length <= n; length++) {
        for (let i = 0; i <= n - length; i++) {
            let j = i + length - 1;
            if (s[i] === s[j]) {
                dp[i][j] = 2 + (i+1 <= j-1 ? dp[i+1][j-1] : 0);
            } else {
                dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]);
            }
        }
    }
    return dp[0][n-1];
}

console.log(longestPalindromicSubsequence('bbbab'));

Line Notes

const dp = Array.from({length: n}, () => Array(n).fill(0));Initialize 2D dp array

dp[i][i] = 1;Single characters are palindromes

for (let length = 2; length <= n; length++) {Loop over substring lengths

if (s[i] === s[j]) {Matching ends add 2 plus inner substring

⏱

Complexity

TimeO(n^2)

SpaceO(n^2)

We fill an n by n table once, each cell computed in O(1).

💡 For n=1000, about 1 million operations, which is efficient.

Interview Verdict: Accepted

This is the standard DP solution for interviews, balancing clarity and efficiency.

🧠

Space Optimized Bottom-Up DP

💡 Since dp[i][j] depends only on dp[i+1][j-1], dp[i+1][j], and dp[i][j-1], we can optimize space by using a 1D array and iterating carefully.

Intuition

Use a single array to store results for substrings ending at different indices, updating from right to left to preserve needed previous states.

Algorithm

1. Initialize a 1D dp array of length n with 1s (single characters).
2. Iterate over start indices i from n-2 down to 0.
3. For each i, iterate end indices j from i+1 to n-1.
4. Use a temporary variable to store dp[i+1][j-1] before updating dp[j].
5. Update dp[j] based on character matches and previous dp values.
6. Return dp[n-1] as the final answer.

💡 The reverse iteration ensures we don't overwrite values needed for future computations.

Recurrence:dp[j] = dp[j-1] + 2 if s[i] == s[j] else max(dp[j], dp[j-1])

</>

Code

def longest_palindromic_subsequence(s):
    n = len(s)
    dp = [1]*n
    for i in range(n-2, -1, -1):
        prev = 0
        for j in range(i+1, n):
            temp = dp[j]
            if s[i] == s[j]:
                dp[j] = 2 + prev
            else:
                dp[j] = max(dp[j], dp[j-1])
            prev = temp
    return dp[n-1]

if __name__ == '__main__':
    print(longest_palindromic_subsequence('bbbab'))

Line Notes

dp = [1]*nInitialize dp for substrings of length 1

for i in range(n-2, -1, -1):Iterate start index backwards to preserve dependencies

temp = dp[j]Store old dp[j] before updating for next iteration

dp[j] = 2 + prevUpdate dp[j] when characters match using prev (dp[i+1][j-1])

public class Solution {
    public static int longestPalindromicSubsequence(String s) {
        int n = s.length();
        int[] dp = new int[n];
        for (int i = 0; i < n; i++) dp[i] = 1;
        for (int i = n - 2; i >= 0; i--) {
            int prev = 0;
            for (int j = i + 1; j < n; j++) {
                int temp = dp[j];
                if (s.charAt(i) == s.charAt(j)) {
                    dp[j] = 2 + prev;
                } else {
                    dp[j] = Math.max(dp[j], dp[j - 1]);
                }
                prev = temp;
            }
        }
        return dp[n - 1];
    }
    public static void main(String[] args) {
        System.out.println(longestPalindromicSubsequence("bbbab"));
    }
}

Line Notes

int[] dp = new int[n];Initialize 1D dp array

for (int i = 0; i < n; i++) dp[i] = 1;Single characters are palindromes

int temp = dp[j];Store old dp[j] before updating

dp[j] = 2 + prev;Update dp[j] when characters match using prev

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int longestPalindromicSubsequence(const string &s) {
    int n = s.size();
    vector<int> dp(n, 1);
    for (int i = n - 2; i >= 0; i--) {
        int prev = 0;
        for (int j = i + 1; j < n; j++) {
            int temp = dp[j];
            if (s[i] == s[j]) {
                dp[j] = 2 + prev;
            } else {
                dp[j] = max(dp[j], dp[j - 1]);
            }
            prev = temp;
        }
    }
    return dp[n - 1];
}

int main() {
    cout << longestPalindromicSubsequence("bbbab") << endl;
    return 0;
}

Line Notes

vector<int> dp(n, 1);Initialize 1D dp vector with 1s

int temp = dp[j];Store old dp[j] before updating

dp[j] = 2 + prev;Update dp[j] when characters match using prev

for (int i = n - 2; i >= 0; i--) {Iterate start index backwards to preserve dependencies

function longestPalindromicSubsequence(s) {
    const n = s.length;
    const dp = new Array(n).fill(1);
    for (let i = n - 2; i >= 0; i--) {
        let prev = 0;
        for (let j = i + 1; j < n; j++) {
            let temp = dp[j];
            if (s[i] === s[j]) {
                dp[j] = 2 + prev;
            } else {
                dp[j] = Math.max(dp[j], dp[j - 1]);
            }
            prev = temp;
        }
    }
    return dp[n - 1];
}

console.log(longestPalindromicSubsequence('bbbab'));

Line Notes

const dp = new Array(n).fill(1);Initialize 1D dp array with 1s

let temp = dp[j];Store old dp[j] before updating

dp[j] = 2 + prev;Update dp[j] when characters match using prev

for (let i = n - 2; i >= 0; i--) {Iterate start index backwards to preserve dependencies

⏱

Complexity

TimeO(n^2)

SpaceO(n)

We use a single array and carefully update it, reducing space from O(n^2) to O(n).

💡 For n=1000, this saves a lot of memory while keeping time efficient.

Interview Verdict: Accepted

This is the most space-efficient DP solution suitable for large inputs.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, code the bottom-up tabulation or memoization approach for clarity and efficiency.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(2^n)	O(n) recursion stack	Yes (deep recursion)	Yes (with extra code)	Mention only - never code
2. Top-Down Memoization	O(n^2)	O(n^2) memo + O(n) recursion stack	Possible for large n	Yes	Good for explaining optimization
3. Bottom-Up Tabulation	O(n^2)	O(n^2)	No	Yes	Best standard approach to code
4. Space Optimized DP	O(n^2)	O(n)	No	Harder	Mention if asked about space optimization

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding all approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Clarify the problem and constraints.Explain the brute force recursive approach to show understanding.Introduce memoization to optimize overlapping subproblems.Present bottom-up tabulation as the standard efficient solution.Discuss space optimization if time permits.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 10min → Test: 3min. Total ~20min

What the Interviewer Tests

Understanding of recursion, DP state definition, ability to optimize with memoization and tabulation, and code correctness.

Common Follow-ups

• Can you reconstruct the longest palindromic subsequence string?
• How would you optimize space usage?
• What changes if we want the count of all palindromic subsequences?
• How does this relate to longest common subsequence?

💡 These follow-ups test deeper understanding and ability to extend or optimize the solution.

🔍

Pattern Recognition

When to Use

1) Problem asks for longest palindromic subsequence or similar palindrome property; 2) Input is a string; 3) Subsequence (not substring) is involved; 4) Overlapping subproblems hint at DP.

Signature Phrases

'longest palindromic subsequence''subsequence that reads the same backward and forward'

NOT This Pattern When

Longest Palindromic Substring problems focus on contiguous substrings and use different DP approaches.

Similar Problems

Longest Common Subsequence - relates by comparing string with its reversePalindrome Partitioning - different problem but also uses palindrome DPLongest Palindromic Substring - substring vs subsequence distinction

Practice

1. Given the following code for computing edit distance, what is the value of dp[3] after the inner loop finishes when word1 = 'abc' and word2 = 'ac' during the second iteration of the outer loop (i=2)?

easy

A. 1

B. 0

C. 3

D. 2

Solution

1. Step 1: Trace dp array initialization and first iteration

   Initially dp = [0,1,2]. After i=1 (word1[0]='a'), dp updates to [1,0,1].

2. Step 2: Trace second iteration i=2 (word1[1]='b')

   Start dp[0]=2. For j=1 (word2[0]='a'), chars differ, dp[1]=min(0+1,2+1,1+1)=1. For j=2 (word2[1]='c'), chars differ, dp[2]=min(1+1,1+1,0+1)=1. So dp after inner loop: [2,1,1].

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Manual step-by-step matches dp[3]=2 [OK]

Hint: Track dp updates carefully for each i,j iteration [OK]

Common Mistakes:

• Off-by-one indexing
• Confusing prev and temp variables
• Mis-updating dp[0]

2. Consider the following Python function implementing a space-optimized DP for longest common substring. What is the returned value when called with s1 = 'abc' and s2 = 'xbc'?

def longest_common_substring_space_optimized(s1, s2):
    n, m = len(s1), len(s2)
    dp = [0] * (m + 1)
    max_len = 0
    for i in range(1, n + 1):
        for j in range(m, 0, -1):
            if s1[i - 1] == s2[j - 1]:
                dp[j] = dp[j - 1] + 1
                if dp[j] > max_len:
                    max_len = dp[j]
            else:
                dp[j] = 0
    return max_len

easy

A. 2

B. 1

C. 3

D. 0

Solution

1. Step 1: Trace dp array updates for i=1 (s1[0]='a')

   Compare 'a' with 'c','b','x' in s2 backwards: no matches, dp remains zeros.

2. Step 2: Trace dp updates for i=2 (s1[1]='b') and i=3 (s1[2]='c')

   At i=2, j=2 matches 'b' == 'b', dp[2] = dp[1]+1=1; max_len=1. At i=3, j=3 matches 'c' == 'c', dp[3] = dp[2]+1=2; max_len=2.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Longest common substring is 'bc' length 2 [OK]

Hint: Trace dp updates backward to avoid overwriting [OK]

Common Mistakes:

• Iterating dp forward overwrites needed values
• Off-by-one indexing errors
• Confusing max_len update timing

3. What is the time complexity of the space-optimized bottom-up DP solution for the longest common substring problem, where n and m are the lengths of the two input strings?

medium

A. O(n * m) due to nested loops comparing all character pairs

B. O(n * m) but with additional O(n + m) recursion stack space

C. O(n * m * min(n, m)) due to checking all substrings explicitly

D. O(n + m) due to single pass over both strings

Solution

1. Step 1: Identify nested loops over n and m

   The algorithm uses two nested loops: outer over n and inner over m, leading to O(n*m) iterations.

2. Step 2: Confirm no recursion or substring extraction

   Space optimization uses iterative DP with O(m) space, no recursion stack or substring extraction, so no extra multiplicative factors.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Nested loops over both strings dominate time complexity [OK]

Hint: Nested loops over both strings imply O(n*m) time [OK]

Common Mistakes:

• Confusing with linear O(n+m)
• Assuming recursion adds stack space
• Thinking substring extraction adds extra factor

4. What is the time complexity of the bottom-up DP solution for Word Break II that uses nested loops over the string and dictionary words, and concatenates sentences stored in dp arrays?

medium

A. O(n^3) due to nested loops and string concatenations

B. O(n^2 * m) because each substring is checked against dictionary words

C. O(2^n) because all segmentations are explored

D. O(n * m) where n = length of string, m = number of words in dictionary

Solution

1. Step 1: Identify nested loops and operations

   Outer loop runs n times, inner loop over dictionary words m times, and for each match, concatenation of strings from dp arrays occurs.

2. Step 2: Analyze concatenation cost

   Concatenation and copying sentences can cost up to O(n) each, and there can be O(n^2) substrings, leading to O(n^3) total time.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Nested loops plus string concatenations cause cubic time [OK]

Hint: String concatenation inside nested loops causes O(n^3) [OK]

Common Mistakes:

• Confusing exponential brute force with DP complexity
• Ignoring concatenation cost

5. Suppose you want to count the number of distinct subsequences of t in s, but now characters in s can be reused multiple times (i.e., you can use the same character in s multiple times to form subsequences). Which modification to the DP approach correctly solves this variant?

hard

A. Use a 2D DP where dp[i][j] counts subsequences using first i chars of s and j chars of t, but allow reusing s[i] by not incrementing i on match

B. Change the recurrence to allow staying at the same i index when matching characters

C. Use the same DP but iterate j forward instead of backward in the inner loop

D. No change needed; original DP already counts subsequences with reuse

Solution

1. Step 1: Understand reuse means characters in s can be used multiple times

   Original DP assumes each character in s can be used at most once per subsequence.

2. Step 2: Modify DP to allow reusing s[i]

   Use 2D DP where dp[i][j] counts subsequences using first i chars of s for first j chars of t, and when s[i] matches t[j], allow staying at i (not incrementing) to reuse character.

3. Step 3: Recognize that iterating j forward or no change won't handle reuse correctly

   Only explicit state allowing reuse by not advancing i on match works.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Allowing reuse requires 2D DP with careful state transitions [OK]

Hint: Reuse means allowing same s[i] multiple times, so must not always increment i

Common Mistakes:

• Assuming original DP handles reuse
• Trying to fix by changing iteration order only