Longest Palindromic Subsequence

📋

Longest Palindromic Subsequence

Edge cases:

</>

IDE

def lps(s: str, i: int, j: int) -> int:public int lps(String s, int i, int j)int lps(const string& s, int i, int j)function lps(s, i, j)

def lps(s, i, j):
    # Write your solution here
    pass

class Solution {
    public int lps(String s, int i, int j) {
        // Write your solution here
        return 0;
    }
}

#include <string>
using namespace std;

int lps(const string& s, int i, int j) {
    // Write your solution here
    return 0;
}

function lps(s, i, j) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: 0Missing base case for empty substring (i > j) returning 0.✅ Add base case: if i > j: return 0.

Wrong: 1 for empty stringIncorrect base case handling, returning 1 when i > j instead of 0.✅ Ensure if i > j: return 0, only if i == j return 1.

Wrong: Less than expected for all identical charsNot adding 2 when s[i] == s[j], or off-by-one in recursion.✅ Use recurrence: if s[i] == s[j]: return 2 + lps(i+1, j-1).

Wrong: Greater than 1 for string with no repeatsGreedy approach picking first matching chars instead of max of two options.✅ When s[i] != s[j], return max(lps(i+1, j), lps(i, j-1)).

Wrong: Output greater than 16 for pairs only stringConfusing 0/1 subsequence with unbounded repetition, counting chars multiple times.✅ Ensure subsequence characters are chosen once; do not reuse indices.

✓

Test Cases

Make sure your base cases handle empty and single character strings correctly.

Test your solution against tricky inputs with no repeats or multiple pairs.

Optimize your solution to use DP to handle large inputs efficiently.

t1_01basic

Input{"s":"bbbab","i":0,"j":4}

Expected4

⏱ Performance - must finish in 2000ms

One longest palindromic subsequence is 'bbbb' with length 4.

💡 Consider comparing characters at the ends and moving inward.

💡 Use recursion or DP to check if s[i] == s[j], then add 2 plus inner subsequence.

💡 If s[i] != s[j], take max of subsequences excluding one end each time.

Why it failed: Incorrect output means the recurrence relation is wrong; ensure to add 2 when s[i] == s[j] and recurse inside, else take max of excluding either end.

✓ Correctly computes longest palindromic subsequence length using proper recurrence.

t1_02basic

Input{"s":"agbdba","i":0,"j":5}

Expected5

⏱ Performance - must finish in 2000ms

Longest palindromic subsequence is 'abdba' with length 5.

💡 Try checking pairs from both ends and use memoization or DP.

💡 Remember to handle cases where characters don't match by taking max of two options.

💡 The subsequence 'abdba' skips 'g' but is palindrome of length 5.

Why it failed: If output is less than 5, likely missed checking both options when characters differ; fix by taking max(lps(i+1,j), lps(i,j-1)).

✓ Correctly identifies longest palindromic subsequence length for mixed characters.

t2_01edge

Input{"s":"","i":0,"j":-1}

Expected0

⏱ Performance - must finish in 2000ms

Empty string has no subsequence, so length is 0.

💡 Check base case when i > j to return 0.

💡 Empty input means no characters to form subsequence.

💡 Return 0 immediately if indices cross.

Why it failed: Returning non-zero for empty string means base case i > j not handled; fix by adding if i > j: return 0.

✓ Correctly returns 0 for empty string base case.

t2_02edge

Input{"s":"z","i":0,"j":0}

Expected1

⏱ Performance - must finish in 2000ms

Single character string is palindrome of length 1.

💡 Check base case when i == j to return 1.

💡 A single character is always a palindrome.

💡 Return 1 immediately if i == j.

Why it failed: If output is not 1 for single character, base case i == j missing; fix by adding if i == j: return 1.

✓ Correctly returns 1 for single character string.

t2_03edge

Input{"s":"aaaaa","i":0,"j":4}

Expected5

⏱ Performance - must finish in 2000ms

All identical characters form palindrome of full length 5.

💡 Check that when s[i] == s[j], add 2 plus inner subsequence.

💡 For identical chars, subsequence can be entire string.

💡 Ensure recursion or DP covers full range when all chars match.

Why it failed: If output less than 5, likely not adding 2 correctly when s[i] == s[j]; fix recurrence to add 2 + lps(i+1, j-1).

✓ Correctly handles all identical characters as full palindrome.

t2_04edge

Input{"s":"abcde","i":0,"j":4}

Expected1

⏱ Performance - must finish in 2000ms

No repeating characters, so longest palindrome subsequence length is 1 (any single char).

💡 Check that when s[i] != s[j], you take max of excluding either end.

💡 Greedy approach picking first matching chars fails here.

💡 Ensure to explore both options and take max, not just first match.

Why it failed: Output >1 means greedy approach picking first match is wrong; fix by taking max(lps(i+1, j), lps(i, j-1)) when chars differ.

✓ Correctly avoids greedy trap and returns 1 for no repeats.

t3_01corner

Input{"s":"bbabcbcab","i":0,"j":8}

Expected7

⏱ Performance - must finish in 2000ms

Longest palindromic subsequence is length 7, e.g. 'babcbab'.

💡 Beware off-by-one errors in indices when recursing.

💡 Check that base cases and recursive calls use correct inclusive indices.

💡 Ensure dp or memo covers full range from i to j inclusive.

Why it failed: Output less than 7 indicates off-by-one error in index handling; fix by ensuring recursion covers s[i..j] inclusive.

✓ Correctly handles inclusive indices and returns 7.

t3_02corner

Input{"s":"aabbccddeeffgghh","i":0,"j":15}

Expected16

⏱ Performance - must finish in 2000ms

Pairs of characters only, longest palindrome subsequence length is 16 (the entire string).

💡 Check that subsequence is 0/1 type, not unbounded repetition.

💡 Do not count multiple occurrences beyond original positions.

💡 Ensure recursion or DP does not reuse characters multiple times.

Why it failed: Output >16 means unbounded repetition bug; fix by ensuring subsequence characters are chosen only once each (0/1 subsequence).

✓ Correctly enforces 0/1 subsequence constraint.

t3_03corner

Input{"s":"abcdecba","i":0,"j":7}

Expected5

⏱ Performance - must finish in 2000ms

Longest palindromic subsequence is 'abcba' with length 5.

💡 Check that you consider all subsequences, not just contiguous substrings.

💡 Avoid greedy picking only first or last characters.

💡 Use DP to explore all pairs and subsequences.

Why it failed: Output less than 5 means greedy or substring-only approach; fix by using full DP over all subsequences.

✓ Correctly finds longest palindromic subsequence beyond substrings.

t4_01performance

Input{"s":"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"}

Expectednull

⏱ Performance - must finish in 2000ms

Input length n=100, O(n^2) DP expected to complete within 2 seconds.

💡 Use bottom-up DP with O(n^2) time complexity.

💡 Avoid pure recursion to prevent exponential time.

💡 Optimize space if possible but ensure O(n^2) time.

Why it failed: TLE indicates exponential or inefficient recursion; fix by implementing DP memoization or bottom-up tabulation.

✓ Algorithm runs within time limit using O(n^2) DP.

Practice

1. You are given a string and need to count all substrings that read the same forwards and backwards. Which approach guarantees an optimal time and space solution for this problem?

easy

A. Use a brute force approach checking every substring with nested loops and palindrome verification.

B. Use a longest common subsequence DP approach comparing the string with its reverse.

C. Expand around each character and each pair of characters to count palindromes in O(n²) time and O(1) space.

D. Apply a greedy approach by extending palindromes only when characters match at the ends.

Solution

1. Step 1: Understand problem constraints

   The problem requires counting all palindromic substrings efficiently, not just longest palindromes.

2. Step 2: Evaluate approaches

   Brute force is correct but inefficient (O(n³)). LCS DP finds longest palindrome but not count of all substrings. Greedy fails on nested palindromes. Expanding around centers counts all palindromes in O(n²) time and O(1) space.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Expanding around centers covers odd and even length palindromes efficiently [OK]

Hint: Expanding centers counts all palindromes in O(n²) time [OK]

Common Mistakes:

• Confusing longest palindrome with counting all palindromic substrings

2. You are given three strings s1, s2, and s3. Determine if s3 can be formed by interleaving the characters of s1 and s2 while preserving the order of characters in each string. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Pure brute force recursion without memoization to explore all character combinations

B. Greedy algorithm that picks characters from s1 or s2 whenever they match s3 sequentially

C. Dynamic Programming using a 2D table to track interleaving possibilities for prefixes of s1 and s2

D. Sorting all strings and then comparing if s3 is a merged sorted string of s1 and s2

Solution

1. Step 1: Understand problem constraints

   The problem requires preserving the order of characters from both s1 and s2 to form s3. This rules out greedy and sorting approaches.

2. Step 2: Identify suitable algorithm

   Dynamic Programming with a 2D table tracks whether prefixes of s1 and s2 can form prefixes of s3, guaranteeing an optimal solution.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   DP ensures all prefix combinations are checked systematically [OK]

Hint: Interleaving requires DP to track prefix matches [OK]

Common Mistakes:

• Assuming greedy works because characters match sequentially
• Thinking sorting helps preserve order

3. Consider the following Python code implementing wildcard matching using space-optimized DP. What is the value of prev[3] after processing i=2 (second character of s='abc') and j=3 (third character of p='a*c')?

easy

A. True

B. Raises an IndexError

C. Depends on previous iteration, cannot determine

D. False

Solution

1. Step 1: Trace dp arrays for i=2, j=3

   At i=2 (s[1]='b'), j=3 (p[2]='c'), since p[j-1] != '*' and not '?', check if s[i-1]==p[j-1]. 'b' != 'c', so curr[3] = False from prev[2].

2. Step 2: Evaluate curr[3]

   At j=2, p[1]='*', so curr[2] can be True if curr[1] or prev[2] is True. However, curr[3] depends on prev[2], which is False at this point, so curr[3] remains False.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   DP correctly updates curr[3] to False at i=2, j=3 [OK]

Hint: Check character matches and '*' propagation carefully [OK]

Common Mistakes:

• Off-by-one indexing
• Confusing curr and prev arrays
• Ignoring '*' propagation

4. The following code attempts to implement the space-optimized DP for longest common substring. Identify the line containing the subtle bug that causes incorrect results on some inputs.

def longest_common_substring_space_optimized_buggy(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(1, m + 1):  # Note: iterating forward
            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

medium

A. Line with 'dp[j] = dp[j - 1] + 1' updating dp

B. Line with 'dp = [0] * (m + 1)' initializing dp array

C. Line with 'if dp[j] > max_len:' updating max_len

D. Line with 'for j in range(1, m + 1):' iterating forward

Solution

1. Step 1: Understand dp array update dependency

   dp[j] depends on dp[j-1] from previous iteration of inner loop, so iterating forward overwrites dp[j-1] before use.

2. Step 2: Identify iteration order bug

   Iterating j forward causes dp[j-1] to be updated before dp[j], corrupting the chain of matching lengths.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Changing inner loop to iterate backward fixes the bug [OK]

Hint: DP update depends on previous dp[j-1], so iterate backward [OK]

Common Mistakes:

• Updating dp forward overwrites needed values
• Incorrect max_len update timing
• Wrong dp initialization size

5. Examine the following buggy code snippet for wildcard matching using space-optimized DP. Which line contains the subtle bug that causes incorrect results on empty strings or patterns?

medium

A. Line 14: curr[j] = curr[j - 1] or prev[j]

B. Line 10: curr = [False] * (n + 1) initialization

C. Line 6: prev[j] = True instead of prev[j] = prev[j - 1]

D. Line 17: curr[j] = prev[j - 1]

Solution

1. Step 1: Analyze initialization of prev array for '*' characters

   Line 6 sets prev[j] = True unconditionally when p[j-1] == '*', which incorrectly assumes all prefixes match.

2. Step 2: Correct initialization logic

   It should propagate previous state: prev[j] = prev[j - 1], ensuring '*' can match empty sequence only if previous prefix matched.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Incorrect initialization causes false positives on empty strings [OK]

Hint: Initialization must propagate previous True states for '*' [OK]

Common Mistakes:

• Setting prev[j] = True blindly
• Ignoring empty string edge cases
• Confusing '*' handling in initialization