Longest Palindromic Substring Solution for Microsoft
Company: Microsoft · Difficulty: Medium · Topics: String, Dynamic Programming
Problem Statement
Given a string s, return the longest palindromic substring in s.
Examples
Example 1:
Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.
Example 2:
Input: s = "cbbd"
Output: "bb"
Explanation: The longest palindromic substring is "bb".
Example 3:
Input: s = "a"
Output: "a"
Explanation: Single character is always a palindrome.
Example 4:
Input: s = "ac"
Output: "a"
Explanation: Either "a" or "c" is a valid answer.
Example 5:
Input: s = "racecar"
Output: "racecar"
Explanation: The entire string is a palindrome.
Intuition
The key insight is that a palindrome can be expanded from its center. For each position in the string, we can try to expand outward to find the longest palindrome centered at that position. We need to handle both odd-length (single character center) and even-length (two character center) palindromes.
Approach
Approach 1: Expand Around Center (Optimal)
1. For each position in the string, expand outward to find palindromes
2. Handle both odd and even length palindromes
3. Keep track of the longest palindrome found
4. Return the substring with maximum length
Approach 2: Dynamic Programming
1. Create a DP table where dp[i][j] indicates if substring(i,j) is palindrome
2. Fill the table using the recurrence: dp[i][j] = (s[i]==s[j]) && dp[i+1][j-1]
3. Track the longest palindrome during the process
Approach 3: Brute Force
1. Check all possible substrings
2. For each substring, check if it's a palindrome
3. Return the longest valid palindrome
Dry Run
Let's trace through Example 1: s = "babad"
Expand Around Center Approach:
- i=0, char='b': expand -> "b" (length=1)
- i=1, char='a': expand -> "a" (length=1)
- i=2, char='b': expand -> "bab" (length=3) - longest so far
- i=3, char='a': expand -> "a" (length=1)
- i=4, char='d': expand -> "d" (length=1)
- Result: "bab"
Solution
Note: This solution provides multiple approaches to solve the problem. Choose the one that best fits your understanding and requirements.
Key Insights:
1. Expand Around Center: Check palindromes from each center position
2. Odd vs Even: Handle both single character and two character centers
3. Early Termination: Stop expanding when characters don't match
Edge Cases:
- Single character: return the character
- Two characters: return the longer palindrome
- All same characters: entire string is palindrome
- No palindromes: return first character
Time Complexity
- Expand Around Center: O(n²)
- Dynamic Programming: O(n²)
- Brute Force: O(n³)
Space Complexity
- Expand Around Center: O(1)
- Dynamic Programming: O(n²)
- Brute Force: O(1)