Longest Palindromic Substring

📋

Longest Palindromic Substring

Edge cases:

</>

IDE

def longest_palindrome_brute(s: str) -> str:public String longestPalindrome(String s)string longestPalindrome(string s)function longestPalindrome(s)

def longest_palindrome_brute(s: str) -> str:
    # Write your solution here
    pass

class Solution {
    public String longestPalindrome(String s) {
        // Write your solution here
        return "";
    }
}

#include <string>
using namespace std;

string longestPalindrome(string s) {
    // Write your solution here
    return "";
}

function longestPalindrome(s) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: empty stringNot initializing max palindrome length to at least 1 or returning empty when no longer palindrome found.✅ Initialize max_len = 1 and start = 0; return s[start:start+max_len].

Wrong: shorter palindrome substringGreedy approach returning first palindrome found instead of longest.✅ Check all centers and update longest palindrome substring only if longer found.

Wrong: incorrect substring boundaries (off-by-one)Incorrect substring slicing indices causing missing last character or wrong length.✅ Ensure substring includes both start and end indices fully: s[start:end+1].

Wrong: fails on even length palindromesOnly expanding around single characters, missing centers between characters.✅ Expand around centers at i and i+1 for even length palindromes.

Wrong: TLE on large inputUsing brute force O(n^3) approach on large input.✅ Implement O(n^2) expand around center or DP approach.

✓

Test Cases

Focus on handling minimal input sizes and uniform strings.

Consider tricky cases that break greedy or naive expansions.

Optimize your solution to avoid cubic time complexity.

t1_01basic

Input{"s":"babad"}

Expected"bab"

⏱ Performance - must finish in 2000ms

The longest palindromic substring is 'bab' (or 'aba'). Both are valid answers; here we expect 'bab'.

💡 Consider checking all substrings and verifying if they are palindromes.

💡 Use dynamic programming or expand around center to optimize palindrome checks.

💡 Track the longest palindrome found and return that substring.

Why it failed: Returned substring is not a palindrome or shorter than the longest palindrome. Fix by verifying palindrome condition correctly and updating max length substring accordingly.

✓ Correctly identifies a longest palindromic substring.

t1_02basic

Input{"s":"cbbd"}

Expected"bb"

⏱ Performance - must finish in 2000ms

The longest palindromic substring is 'bb' in 'cbbd'.

💡 Check palindromes centered at each character and between characters.

💡 Remember even length palindromes need special handling.

💡 Expand around centers and update longest substring when longer palindrome found.

Why it failed: Fails to detect even-length palindrome. Fix by expanding around centers between characters as well as at characters.

✓ Correctly handles even-length palindromes.

t2_01edge

Input{"s":"a"}

Expected"a"

⏱ Performance - must finish in 2000ms

Single character string is itself the longest palindrome.

💡 Check if your code handles strings of length 1 correctly.

💡 A single character is always a palindrome.

💡 Return the input string directly if length is 1.

Why it failed: Fails on single character input by returning empty or incorrect substring. Fix by handling base case where string length is 1.

✓ Correctly returns single character string as palindrome.

t2_02edge

Input{"s":"aaaaaa"}

Expected"aaaaaa"

⏱ Performance - must finish in 2000ms

All characters same, entire string is the longest palindrome.

💡 Check if your code can handle strings where all characters are identical.

💡 The entire string should be returned as it is a palindrome.

💡 Ensure your palindrome expansion does not stop prematurely.

Why it failed: Fails to return entire string when all characters are same. Fix by correctly expanding palindrome boundaries without early termination.

✓ Correctly returns entire string when all characters are identical.

t2_03edge

Input{"s":"abcde"}

Expected"a"

⏱ Performance - must finish in 2000ms

No palindrome longer than 1, any single character is valid; here 'a' is expected.

💡 Check if your code handles cases with no palindromes longer than 1.

💡 Return the first character or any single character substring.

💡 Ensure your code does not return empty string in such cases.

Why it failed: Returns empty string or incorrect substring when no palindrome longer than 1 exists. Fix by initializing max palindrome length to 1 and returning a single character substring.

✓ Correctly returns a single character substring when no longer palindrome exists.

t2_04edge

Input{"s":"racecar"}

Expected"racecar"

⏱ Performance - must finish in 2000ms

Palindrome at the start and end of string; entire string is palindrome.

💡 Check if your code correctly identifies palindromes spanning entire string.

💡 Expand around center carefully to cover full length.

💡 Update longest palindrome substring when full string is palindrome.

Why it failed: Fails to detect palindrome spanning entire string. Fix by expanding palindrome boundaries fully and updating longest substring accordingly.

✓ Correctly identifies full string palindrome.

t3_01corner

Input{"s":"abacdfgdcaba"}

Expected"aba"

⏱ Performance - must finish in 2000ms

Longest palindrome is 'aba' at start or end; tests greedy approach that picks longest prefix palindrome only.

💡 Beware of greedy approaches that pick first palindrome found.

💡 Check all centers for palindrome expansion.

💡 Track and update longest palindrome substring globally.

Why it failed: Greedy approach returns first palindrome found instead of longest. Fix by checking all possible centers and updating longest palindrome accordingly.

✓ Correctly finds longest palindrome despite multiple palindromes present.

t3_02corner

Input{"s":"abcbaefgfe"}

Expected"abcba"

⏱ Performance - must finish in 2000ms

Tests off-by-one errors in palindrome expansion; longest palindrome is 'efgfe' at end.

💡 Check palindrome expansion boundaries carefully.

💡 Ensure indices do not go out of range during expansion.

💡 Update longest palindrome substring only when strictly longer.

Why it failed: Off-by-one error causes shorter palindrome or wrong substring returned. Fix by correctly expanding indices and updating longest substring only if longer.

✓ Correctly handles palindrome boundaries and returns longest substring.

t3_03corner

Input{"s":"abccba"}

Expected"abccba"

⏱ Performance - must finish in 2000ms

Tests confusion between 0/1 indexing or substring boundaries; entire string is palindrome.

💡 Be careful with substring start and end indices.

💡 Confirm palindrome check includes both ends correctly.

💡 Return substring from start index to end index inclusive.

Why it failed: Incorrect substring boundaries cause missing last character or off-by-one length. Fix by ensuring substring includes both start and end indices fully.

✓ Correctly returns entire palindrome substring with proper boundaries.

t4_01performance

Input{"s":"aaaaaaaaaabaaaaaaaaaabaaaaaaaaaa"}

Expectednull

⏱ Performance - must finish in 2000ms

Input length n=29, O(n^2) DP or expand around center expected to complete within 2s; brute force O(n^3) will TLE.

💡 Brute force O(n^3) is too slow for large n.

💡 Use expand around center or DP with O(n^2) time complexity.

💡 Avoid checking all substrings explicitly.

Why it failed: TLE due to O(n^3) brute force approach. Fix by implementing O(n^2) expand around center or DP solution.

✓ Efficient O(n^2) solution passes within time limit.

Practice

1. Consider the following code snippet for counting distinct subsequences of t in s. What is the final returned value when s = "abc" and t = "ac"?

easy

A. 0

B. 1

C. 3

D. 2

Solution

1. Step 1: Trace dp array updates for s="abc", t="ac"

   Initialize dp=[1,0,0]. Iteration i=1 (s[0]='a'): j=2 no match, j=1 matches t[0]='a', dp[1]+=dp[0]=1 -> dp=[1,1,0].

2. Step 2: Continue tracing for i=2 (s[1]='b') and i=3 (s[2]='c')

   i=2 no matches, dp unchanged. i=3 matches t[1]='c', dp[2]+=dp[1]=0+1=1 -> dp=[1,1,1]. Final dp[n]=dp[2]=1.

3. Step 3: Count all subsequences matching "ac"

   Subsequences: "ac" only, total 1.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   dp array correctly counts 1 subsequence [OK]

Hint: Trace dp array backward updates carefully [OK]

Common Mistakes:

• Off-by-one errors in indices
• Forgetting to iterate j backward

2. You need to transform one string into another using the minimum number of insertions, deletions, and substitutions. Which algorithmic approach guarantees finding the optimal solution efficiently?

easy

A. Dynamic Programming that builds solutions for all prefixes of both strings

B. Greedy algorithm that replaces characters whenever they differ

C. Divide and conquer by splitting strings at midpoint and solving recursively

D. Backtracking all possible sequences of edits without memoization

Solution

1. Step 1: Understand problem requires minimal edits including insertions, deletions, and substitutions

   These operations depend on overlapping subproblems, making DP suitable.

2. Step 2: Identify approach that solves all subproblems efficiently

   Dynamic Programming computes minimal edits for all prefixes, ensuring optimality and polynomial time complexity.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   DP covers all prefix pairs systematically [OK]

Hint: Optimal edit distance requires DP over all prefix pairs [OK]

Common Mistakes:

• Assuming greedy always works
• Thinking divide and conquer alone suffices
• Ignoring overlapping subproblems

3. You need to determine if a given input string matches a pattern that includes '.' which matches any single character, and '*' which matches zero or more of the preceding element. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Dynamic Programming using a 2D table or space-optimized 1D array

B. Sorting the pattern and string then comparing character by character

C. Backtracking with pruning based on character classes

D. Greedy matching scanning the string once from left to right

Solution

1. Step 1: Understand problem constraints

   The pattern includes '*' which can match zero or more of the preceding element, and '.' which matches any single character. This requires checking multiple matching possibilities.

2. Step 2: Identify algorithmic approach

   Greedy or sorting approaches fail because '*' can match variable-length substrings and '.' matches any character. Backtracking is exponential in worst case. Dynamic Programming efficiently stores intermediate results to avoid recomputation, guaranteeing optimal solution.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   DP handles overlapping subproblems and variable-length matches [OK]

Hint: DP handles variable-length '*' matches optimally [OK]

Common Mistakes:

• Assuming greedy works for '*' patterns

4. Consider the following Python code implementing the space-optimized DP solution for maximum uncrossed lines. What is the value of dp after the outer loop completes for i=2 when nums1 = [1,4,2] and nums2 = [1,2,4]?

easy

A. [0, 1, 2, 2]

B. [0, 1, 1, 1]

C. [0, 1, 1, 2]

D. [0, 0, 1, 1]

Solution

1. Step 1: Trace dp after i=1

   For i=1 (nums1[0]=1), dp updates to [0,1,1,1] because nums2 has 1 at j=1, matches increment dp[1].

2. Step 2: Trace dp after i=2

   For i=2 (nums1[1]=4), dp updates as follows: - j=1: no match, dp[1]=max(dp[1], dp[0])=1 - j=2: no match, dp[2]=max(dp[2], dp[1])=1 - j=3: match (4==4), dp[3]=prev+1=1+1=2 where prev is dp[2] before update which was 1, so dp after i=2 is [0,1,1,2].

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Matches at positions (1,1) and (2,3) give dp[3]=2 after i=2 [OK]

Hint: Track prev and dp[j] carefully to avoid off-by-one errors [OK]

Common Mistakes:

• Confusing prev and dp[j] updates
• Off-by-one indexing in dp array

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