Longest Palindromic Substring - Leetcode Solution

Problem Statement:

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

A palindrome is a word, phrase, number, or other sequence of characters that reads the same backward as forward. For example, "madam" is a palindrome.

Example 1:

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

Example 2:

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

Example 3:

Input: s = "a" Output: "a"

Example 4:

Input: s = "ac" Output: "a"

Approach:

We can use the approach of expanding around center. We can imagine that for each character in the string, there are possibly 2n - 1 palindromes, where n is the length of the string. For example, given the string "abc", we can create the following palindromes: "a", "b", "c", "aa", "bb", "cc", "aba", "abcba", "bab", "bcb". This gives us a brute force approach of checking each substring to see if it is a palindrome and keeping track of the longest one found so far. However, this approach has a time complexity of O(n^3) since we have to check each substring and for each substring, we have to check if it is a palindrome.

To improve this algorithm, we can use the expanding around center approach. We start by considering each character in the string as the center of a potential palindrome and expand outwards from the center. We can do this for both odd and even length palindromes. For example, for string "abcba", we can consider the center to be "c" and expand outwards to get the palindrome "abcba". We can also consider "cb" as the center and expand outwards to get the palindrome "bcb". We keep track of the longest palindrome found so far and return it at the end.

Solution:

class Solution { public: string longestPalindrome(string s) { int n = s.length(); if (n == 0) return ""; string longest = s.substr(0, 1); for (int i = 0; i < n - 1; i++) { string p1 = expandAroundCenter(s, i, i); if (p1.length() > longest.length()) longest = p1; string p2 = expandAroundCenter(s, i, i + 1); if (p2.length() > longest.length()) longest = p2; } return longest; } private: string expandAroundCenter(string s, int c1, int c2) { int l = c1, r = c2; int n = s.length(); while (l >= 0 && r <= n - 1 && s[l] == s[r]) { l--; r++; } return s.substr(l + 1, r - l - 1); } };

Time Complexity:

The time complexity of this algorithm is O(n^2) because we have two nested loops and for each iteration of the outer loop, we expand around center which takes O(n) time.

Space Complexity:

The space complexity of this algorithm is O(1) because we are not using any extra data structures to store information. We are only using constant space to store variables and return values.

Note:

This algorithm can be further optimized by using Manacher's algorithm which has a time complexity of O(n) and space complexity of O(n). However, the implementation of Manacher's algorithm is more complex than this expanding around center approach.

1