Longest Palindromic Substring

LeetCode 5 | Difficulty: Medium

Medium

Problem Description

Given a string s, return the longest palindromic substring in s.

Example 1:

Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.

Example 2:

Input: s = "cbbd"
Output: "bb"

Constraints:

- `1 <= s.length <= 1000`

- `s` consist of only digits and English letters.

Topics: Two Pointers, String, Dynamic Programming

---

Approach

Dynamic Programming

Break the problem into overlapping subproblems. Define a state (what information do you need?), a recurrence (how does state[i] depend on smaller states?), and a base case. Consider both top-down (memoization) and bottom-up (tabulation) approaches.

When to use

Optimal substructure + overlapping subproblems (counting ways, min/max cost, feasibility).

---

Solutions

Solution 1: C# (Best: 92 ms)

Metric	Value
Runtime	92 ms
Memory	23.2 MB
Date	2020-06-12

Solution

public class Solution {
    public string LongestPalindrome(string s) {
        if(string.IsNullOrEmpty(s)) return s;
    int len = s.Length;
    int maxLen = 0;
    int start = 0;

    for (int i = 0; i < len; i++)
    {
        ExpandAroundCenter(s, i, i, ref start, ref maxLen);
        ExpandAroundCenter(s, i, i+1, ref start, ref maxLen);           
    }
    return s.Substring(start, maxLen);
}

public void ExpandAroundCenter(string s, int low, int high, ref int start, ref int maxLen)
{
    while (low >= 0 && high < s.Length && s[low] == s[high])
    {
        low--;
        high++;
    }
    
    low++;
    high--;
    
    if (high - low + 1 > maxLen)
    {
        start = low;
        maxLen = high - low + 1;
    }
}
}

📜 2 more C# submission(s)

Submission (2018-07-05) — 112 ms, N/A

public class Solution {
    public string LongestPalindrome(string s) {
        if(string.IsNullOrEmpty(s)) return s;
    int len = s.Length;
    int maxLen = 0;
    int start = 0;

    for (int i = 0; i < len; i++)
    {
        ExpandAroundCenter(s, i, i, ref start, ref maxLen);
        ExpandAroundCenter(s, i, i+1, ref start, ref maxLen);           
    }
    return s.Substring(start, maxLen);
}

public void ExpandAroundCenter(string s, int low, int high, ref int start, ref int maxLen)
{
    while (low >= 0 && high < s.Length && s[low] == s[high])
    {
        low--;
        high++;
    }
    if (high - low - 1 > maxLen)
    {
        start = low + 1;
        maxLen = high - low - 1;
    }
}
}

Submission (2017-07-11) — 162 ms, N/A

public class Solution {
    public string LongestPalindrome(string s) {
        int len = s.Length;
        int maxLen = 1;
        int start = 0;
        int low = 0, high = 0;
        
        for(int i=1;i<len;i++)
        {
            //even case 
            low = i-1;
            high = i;
            while(low >= 0 && high < len && s[low] ==  s[high])
            {
                if(high - low + 1 > maxLen)
                {
                    start = low ;
                    maxLen = high - low + 1;
                }
                low--;
                high++;
            }
            
            low = i-1;
            high = i+1;
            while(low >= 0 && high < len && s[low] ==  s[high])
            {
                if(high - low + 1 > maxLen)
                {
                    start = low ;
                    maxLen = high - low + 1;
                }
                low--;
                high++;
            }
            
            
        }
        
        return s.Substring(start, maxLen);
        
    }
}

---

Complexity Analysis

Approach	Time	Space
Two Pointers	$O(n)$	$O(1)$
Dynamic Programming	$O(n)$	$O(n)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• Define the DP state clearly. Ask: "What is the minimum information I need to make a decision at each step?"
• Consider if you can reduce space by only keeping the last row/few values.
• LeetCode provides 3 hint(s) for this problem — try solving without them first.

💡 Hints

Hint 1: How can we reuse a previously computed palindrome to compute a larger palindrome?

Hint 2: If “aba” is a palindrome, is “xabax” a palindrome? Similarly is “xabay” a palindrome?

Hint 3: Complexity based hint: If we use brute-force and check whether for every start and end position a substring is a palindrome we have O(n^2) start - end pairs and O(n) palindromic checks. Can we reduce the time for palindromic checks to O(1) by reusing some previous computation.