Longest Palindromic Substring

▶

Steps

setup

Initialize DP Table and Variables

Create a 5x5 DP table initialized with false, and set start=0 and max_len=1 to track the longest palindrome found so far.

💡 Initializing the DP table and variables sets the foundation for marking palindromic substrings.

Line:

n = len(s)
dp = [[false] * n for _ in range(n)]
start, max_len = 0, 1

💡 We need a table to record palindrome status for all substrings and variables to track the longest palindrome.

fill_cells

Mark Single Characters as Palindromes

Mark all substrings of length 1 (single characters) as true in the DP table because any single character is a palindrome.

💡 Single characters are the simplest palindromes and serve as the base case for longer substrings.

Line:

for i in range(n):
    dp[i][i] = true

💡 Every single character substring is a palindrome, so dp[i][i] = true for all i.

fill_cells

Check Substring of Length 2: i=0, j=1

Check substring 'ba' (indices 0 to 1). Since s[0] != s[1], mark dp[0][1] as false.

💡 Substrings of length 2 are palindromes only if both characters are equal.

Line:

length = 2
for i in range(n - length + 1):
    j = i + length - 1
    if s[i] == s[j]:
        dp[i][j] = true
    else:
        dp[i][j] = false

💡 Two-character substrings require matching characters to be palindromes.

fill_cells

Check Substring of Length 2: i=1, j=2

Check substring 'ab' (indices 1 to 2). Since s[1] != s[2], mark dp[1][2] as false.

💡 Again, two characters must match to be palindrome.

Line:

if s[i] == s[j]:
    dp[i][j] = true
else:
    dp[i][j] = false

💡 Non-matching pairs of length 2 are not palindromes.

fill_cells

Check Substring of Length 2: i=2, j=3

Check substring 'ba' (indices 2 to 3). Since s[2] != s[3], mark dp[2][3] as false.

💡 Two-character substrings must have equal characters to be palindrome.

Line:

if s[i] == s[j]:
    dp[i][j] = true
else:
    dp[i][j] = false

💡 Non-palindromic substring of length 2.

fill_cells

Check Substring of Length 2: i=3, j=4

Check substring 'ad' (indices 3 to 4). Since s[3] != s[4], mark dp[3][4] as false.

💡 Two-character substrings must have equal characters to be palindrome.

Line:

if s[i] == s[j]:
    dp[i][j] = true
else:
    dp[i][j] = false

💡 Non-palindromic substring of length 2.

fill_cells

Check Substring of Length 3: i=0, j=2

Check substring 'bab' (indices 0 to 2). Since s[0] == s[2] and length <= 3, mark dp[0][2] as true and update longest palindrome to length 3 starting at 0.

💡 For length 3, if the first and last characters match, substring is palindrome.

Line:

if s[i] == s[j]:
    if length <= 3:
        dp[i][j] = true

💡 Found a palindrome longer than previous max length.

fill_cells

Check Substring of Length 3: i=1, j=3

Check substring 'aba' (indices 1 to 3). Since s[1] == s[3] and length <= 3, mark dp[1][3] as true and update longest palindrome to length 3 starting at 1.

💡 Another length 3 palindrome found with matching ends.

Line:

if s[i] == s[j]:
    if length <= 3:
        dp[i][j] = true

💡 Found another palindrome of max length 3, overlapping previous one.

fill_cells

Check Substring of Length 3: i=2, j=4

Check substring 'bad' (indices 2 to 4). Since s[2] != s[4], mark dp[2][4] as false.

💡 Characters must match to be palindrome.

Line:

else:
    dp[i][j] = false

💡 Substring 'bad' is not palindrome.

fill_cells

Check Substring of Length 4: i=0, j=3

Check substring 'baba' (indices 0 to 3). Since s[0] != s[3], mark dp[0][3] as false.

💡 For length > 3, substring is palindrome only if ends match and inner substring is palindrome.

Line:

if s[i] == s[j]:
    dp[i][j] = dp[i+1][j-1]
else:
    dp[i][j] = false

💡 Substring 'baba' is not palindrome.

fill_cells

Check Substring of Length 4: i=1, j=4

Check substring 'abad' (indices 1 to 4). Since s[1] != s[4], mark dp[1][4] as false.

💡 Ends must match for palindrome of length > 3.

Line:

else:
    dp[i][j] = false

💡 Substring 'abad' is not palindrome.

fill_cells

Check Substring of Length 5: i=0, j=4

Check substring 'babad' (indices 0 to 4). Since s[0] != s[4], mark dp[0][4] as false.

💡 Longest substring checked last; ends must match and inner substring palindrome.

Line:

else:
    dp[i][j] = false

💡 Full string is not palindrome.

reconstruct

Return Longest Palindromic Substring

Return the substring starting at index 0 with length 3, which is 'bab'.

💡 The longest palindrome found is 'bab' from indices 0 to 2.

Line:

return s[start:start + max_len]

💡 The DP table helped identify the longest palindrome substring.

def longest_palindrome_dp(s: str) -> str:
    n = len(s)  # STEP 1
    if n == 0:
        return ""
    dp = [[false] * n for _ in range(n)]  # STEP 1
    start, max_len = 0, 1  # STEP 1

    for i in range(n):  # STEP 2
        dp[i][i] = true

    for length in range(2, n + 1):  # STEP 3-12
        for i in range(n - length + 1):
            j = i + length - 1
            if s[i] == s[j]:
                if length <= 3:
                    dp[i][j] = true  # STEP 7,8
                else:
                    dp[i][j] = dp[i + 1][j - 1]  # STEP 10
            else:
                dp[i][j] = false  # STEP 3-6,9,11,12

            if dp[i][j] and length > max_len:
                start = i  # STEP 7,8
                max_len = length  # STEP 7,8

    return s[start:start + max_len]  # STEP 13

📊

Longest Palindromic Substring - Watch the Algorithm Execute, Step by Step

Watching the table fill reveals how smaller palindrome results build up to larger ones, making the logic crystal clear.

Item 0 - wt:0 val:0

i\w	0	1	2	3	4
i=0
i=1
i=2
i=3
i=4

Item 0 - wt:0 val:0

i\w	0	1	2	3	4
i=0
i=1
i=2
i=3
i=4

s[0] = 'b' palindrome

Item 0 - wt:0 val:0

i\w	0	1	2	3	4
i=0
i=1
i=2
i=3
i=4

'b' != 'a'

Item 1 - wt:0 val:0

i\w	0	1	2	3	4
i=0
i=1
i=2
i=3
i=4

'a' != 'b'

Item 2 - wt:0 val:0

i\w	0	1	2	3	4
i=0
i=1
i=2
i=3
i=4

'b' != 'a'

Item 3 - wt:0 val:0

i\w	0	1	2	3	4
i=0
i=1
i=2
i=3
i=4

'a' != 'd'

Item 0 - wt:0 val:0

i\w	0	1	2	3	4
i=0
i=1
i=2
i=3
i=4

'bab' palindrome

Item 1 - wt:0 val:0

i\w	0	1	2	3	4
i=0
i=1
i=2
i=3
i=4

'aba' palindrome

Item 2 - wt:0 val:0

i\w	0	1	2	3	4
i=0
i=1
i=2
i=3
i=4

'b' != 'd'

Item 0 - wt:0 val:0

i\w	0	1	2	3	4
i=0
i=1
i=2
i=3
i=4

'b' != 'a'

Item 1 - wt:0 val:0

i\w	0	1	2	3	4
i=0
i=1
i=2
i=3
i=4

'a' != 'd'

Item 0 - wt:0 val:0

i\w	0	1	2	3	4
i=0
i=1
i=2
i=3
i=4

'b' != 'd'

Item 0 - wt:0 val:0

i\w	0	1	2	3	4
i=0
i=1
i=2
i=3
i=4

Longest palindrome 'bab'

Key Takeaways

✓ The DP table diagonal represents all single-character palindromes.

This base case is easy to overlook but is essential for building longer palindromes.

✓ Two-character substrings are palindromes only if both characters match.

This step bridges the base case and the general case, showing how the table starts to fill beyond single characters.

✓ For substrings longer than 3, palindrome status depends on the substring inside the ends.

This dependency is the core insight of the DP approach and is visually clear when watching the table fill diagonally.

Practice

1. You are given two strings and need to find the shortest string that contains both as subsequences. Which algorithmic approach guarantees finding this shortest common supersequence efficiently?

easy

A. Greedy approach that merges characters from both strings whenever they differ

B. Dynamic programming based on longest common subsequence to build the shortest supersequence

C. Pure brute force recursion enumerating all supersequences and selecting the shortest

D. Sorting characters of both strings and merging them in lexicographical order

Solution

1. Step 1: Understand the problem requires minimal length supersequence containing both strings as subsequences

   Greedy or sorting approaches fail because they do not consider subsequence order constraints.

2. Step 2: Recognize that longest common subsequence (LCS) helps identify overlapping parts to minimize duplication

   Dynamic programming using LCS length allows building the shortest common supersequence efficiently.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   LCS-based DP is the classic and optimal approach for shortest common supersequence [OK]

Hint: Shortest common supersequence uses LCS-based DP [OK]

Common Mistakes:

• Thinking greedy merging always works
• Confusing substring with subsequence
• Assuming sorting helps

2. The following code attempts to count palindromic substrings by expanding around centers. Identify the line containing the subtle bug that causes incorrect counts for even-length palindromes.

def countSubstrings(s: str) -> int:
    n = len(s)
    count = 0

    def expand(left, right):
        nonlocal count
        while left >= 0 and right < n and s[left] == s[right]:
            count += 1
            left -= 1
            right += 1

    for i in range(n):
        expand(i, i)      # Odd length palindromes
        expand(i, i)      # Even length palindromes (bug here)

    return count

medium

A. Line calling expand(i, i) for even length palindromes

B. Line calling expand(i, i) for odd length palindromes

C. Line decrementing left inside expand function

D. Line incrementing right inside expand function

Solution

1. Step 1: Understand even length palindrome expansion

   Even length palindromes require expanding around two adjacent indices, i and i+1.

2. Step 2: Identify incorrect call

   Calling expand(i, i) twice means even length expansions are not checked; should be expand(i, i+1).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Even length palindromes like "aa" missed due to wrong center [OK]

Hint: Even length palindromes need expand(i, i+1) call [OK]

Common Mistakes:

• Using same indices for odd and even expansions

3. The following code attempts to count distinct subsequences of t in s using space-optimized DP. Which line contains a subtle bug that causes incorrect results on some inputs?

medium

A. Line 6: dp = [0] * (n + 1)

B. Line 9: for j in range(1, n + 1): # iterating forwards

C. Line 4: dp[0] = 1

D. Line 10: if s[i - 1] == t[j - 1]:

Solution

1. Step 1: Identify iteration direction over dp array

   The inner loop iterates j forwards from 1 to n, which causes dp[j-1] to be overwritten before use.

2. Step 2: Understand consequence of forward iteration

   Forward iteration corrupts dp values needed for correct counting, leading to undercount or overcount of subsequences.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Correct code iterates j backward to preserve dp[j-1] values [OK]

Hint: Inner loop must iterate backward to avoid overwriting dp[j-1] [OK]

Common Mistakes:

• Iterating dp array forwards in space-optimized DP

4. What is the time and space complexity of the space-optimized bottom-up DP solution for the Minimum ASCII Delete Sum problem, given strings of lengths m and n?

medium

A. Time: O(m+n), Space: O(m+n)

B. Time: O(m*n), Space: O(n)

C. Time: O(m*n), Space: O(m*n)

D. Time: O(2^(m+n)), Space: O(m+n)

Solution

1. Step 1: Identify nested loops

   Outer loop runs m times, inner loop runs n times -> total O(m*n) time.

2. Step 2: Analyze space usage

   Only one dp array of size n+1 is used, so space is O(n).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Matches known DP optimization for string problems [OK]

Hint: Nested loops multiply time; dp array size defines space [OK]

Common Mistakes:

• Confusing recursion stack space with DP array space

5. Suppose you want to count palindromic substrings in a string where characters can be replaced any number of times (reusable characters). Which modification to the expand around center approach correctly handles this variant?

hard

A. No modification needed; the original expand around center approach already counts palindromes with replacements.

B. Modify expand to allow skipping mismatched characters to find palindromes with replacements.

C. Precompute all possible character replacements and run the original expand around center for each variant.

D. Use dynamic programming with memoization to store counts for substrings allowing character replacements.

Solution

1. Step 1: Understand the variant

   Allowing character replacements means palindrome checks must consider substitutions, not exact matches.

2. Step 2: Evaluate approaches

   Expand around center relies on exact matches; skipping mismatches breaks palindrome definition. Precomputing all variants is exponential. DP with memoization can track allowed replacements efficiently.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   DP can handle flexible palindrome definitions with substitutions [OK]

Hint: Exact match expansion fails when replacements allowed [OK]

Common Mistakes:

• Assuming original approach works without changes