Leetcode 5. Longest Palindromic Substring

medium

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"

Idea

sweep from the start of the string to the end, while checking from that position to left and right, characters are equal

Solution

class Solution {
public:
    string longestPalindrome(string s) {
        int best_length = 0;
        string best_string;
        auto f = [&](int l, int r){
            while( l>=0 && r<s.length() && s[l] == s[r]) {
                if ( r - l + 1 > best_length) {
                    best_length = r - l + 1;
                    best_string = s.substr(l, r - l + 1);
                }
                l--;
                r++;
            }   
        };
        for (int i=0; i< s.length(); i++) {
            f(i, i);   // for odd
            f(i, i+1); // for even
        }
        return best_string;
    }
};