Longest Palindromic Substring

Problem

Given a string s, return the longest substring of s that is a palindrome.

A palindrome is a string that reads the same forward and backward.

If there are multiple palindromic substrings that have the same length, return any one of them.

Examples

Example 1:

Input: s = "ababd"

Output: "bab"

Explanation: Both “aba” and “bab” are valid answers.

Example 2:

Input: s = "abbc"

Output: "bb"

Constraints

• 1 <= s.length <= 1000
• s contains only digits and English letters.

You should aim for a solution as good or better than O(n^2) time and O(1) space, where n is the length of the given string.

Solution

Do a 2 pointer walk, where outer index is the start of the left pointer. We need to handle 2 cases for even and odd.

class Solution {
public:
    string longestPalindrome(const string &s) {
        int res_idx = 0;
        int res_len = 0;
        // index is the center of the palindrome
        for (int i = 0; i < s.size(); ++i) {
            // Odd length, i is the center, and do a 2 pointer walk
            int l = i; 
            int r =  i;
            while (l >= 0 && r < s.size() && s[l] == s[r]) {
                if (r - l + 1 > res_len) {
                    res_len = r - l + 1;
                    res_idx = l;
                }
                --l;
                ++r;
            }
            // Even length, left starts at i and right starts one off
            l = i;
            r = i + 1;
            while (l >= 0 && r < s.size() && s[l] == s[r]) {
                if (r - l + 1 > res_len) {
                    res_len = r - l + 1;
                    res_idx = l;
                }
                --l;
                ++r;
            }
        }
        return s.substr(res_idx, res_len);
    }
};