Longest Palindromic Substring (opens in a new tab) Medium

Problem

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

Example

Input: s = "babad"

Output: "bab"

Note: "aba" is also a valid answer.

Summary

To solve this problem, we can iterate through the input string, and for each character, expand around it to find the longest palindromic substring that includes it. We will do this for both even and odd length palindromes. We will keep track of the start and end indices of the longest palindrome found so far.

Solution

In TypeScript

function longestPalindrome(s: string): string {
	let start = 0;
	let end = 0;
 
	for (let i = 0; i < s.length; i++) {
		const len1 = expandAroundCenter(s, i, i);
		const len2 = expandAroundCenter(s, i, i + 1);
		const len = Math.max(len1, len2);
 
		if (len > end - start) {
			start = i - Math.floor((len - 1) / 2);
			end = i + Math.floor(len / 2);
		}
	}
 
	return s.substring(start, end + 1);
}
 
function expandAroundCenter(s: string, left: number, right: number): number {
	while (left >= 0 && right < s.length && s[left] === s[right]) {
		left--;
		right++;
	}
 
	return right - left - 1;
}

In Python

def longestPalindrome(self, s: str) -> str:
		start = 0
		end = 0
 
		for i in range(len(s)):
				len1 = self.expandAroundCenter(s, i, i)
				len2 = self.expandAroundCenter(s, i, i + 1)
				length = max(len1, len2)
 
				if length > end - start:
						start = i - (length - 1) // 2
						end = i + length // 2
 
		return s[start:end + 1]
 
def expandAroundCenter(self, s: str, left: int, right: int) -> int:
		while left >= 0 and right < len(s) and s[left] == s[right]:
				left -= 1
				right += 1
 
		return right - left - 1

Step-by-step explanation

1. Initialize two variables start and end to store the indices of the longest palindrome found so far.

let start = 0;
let end = 0;

2. Iterate through the input string s with a for loop, using variable i as the index. For each character at index i in the string, we will try to expand around it to find the longest palindromic substring that includes it.

for (let i = 0; i < s.length; i++) {
	// ...
}

3. Call the expandAroundCenter function twice for each character, once for odd-length palindromes and once for even-length palindromes. We pass i as the center for odd-length palindromes and i + 1 for even-length palindromes.

const len1 = expandAroundCenter(s, i, i);
const len2 = expandAroundCenter(s, i, i + 1);

4. The expandAroundCenter function returns the length of the longest palindrome found when expanding around the given center(s). We take the maximum of the two returned lengths (odd and even cases) as the actual length of the longest palindrome for the current character.

const len = Math.max(len1, len2);

5. If the length of the palindrome found is greater than the length of the previously found longest palindrome (tracked using the start and end variables), update the start and end variables to represent the new longest palindrome.

if (len > end - start) {
		start = i - Math.floor((len - 1) / 2);
		end = i + Math.floor(len / 2);
}

6. After the loop finishes, we return the longest palindromic substring using s.substring(start, end + 1).

return s.substring(start, end + 1);

7. The expandAroundCenter function is a helper function that takes the string s and two indices, left and right, as input. It tries to expand around the center of the palindrome, checking if the characters at left and right are equal. If they are, it continues expanding until they are not equal or we reach the boundaries of the string. The function then returns the length of the palindrome found.

function expandAroundCenter(s: string, left: number, right: number): number {
		while (left >= 0 && right < s.length && s[left] === s[right]) {
				left--;
				right++;
		}
 
		return right - left - 1;
}

Complexity Analysis

Time Complexity

The time complexity of this solution is O(n^2), where n is the length of the input string. In the worst case, we expand around each character, taking linear time for each character, resulting in quadratic time complexity.

Space Complexity

The space complexity of this solution is O(1), as we only use a few variables to keep track of the start and end indices, and no additional data structures are used.