5. Longest Palindromic Substring

https://leetcode.com/problems/longest-palindromic-substring/

Problem

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

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"

Constraints:

• 1 <= s.length <= 1000

• s consist of only digits and English letters (lower-case and/or upper-case),

Solution

class Solution {
public:
    string longestPalindrome(string s) {
        if (s.empty()) return s;
        pair<int, int> indice{0,0};
        for (int i = 1; i < s.size(); ++i) {
            pair<int, int> cand1 = expand(s, i - 1, i);
            pair<int, int> cand2 = expand(s, i, i);
            if (cand1.second - cand1.first > indice.second - indice.first) indice = cand1;
            if (cand2.second - cand2.first > indice.second - indice.first) indice = cand2;
        }
        return s.substr(indice.first, indice.second - indice.first + 1);
    }
    inline pair<int, int> expand(string &s, int begin, int end) {
        if (s[begin] != s[end]) return make_pair(0, 0);
        while (0 <= begin - 1 && end + 1 < s.size() && s[begin - 1] == s[end + 1]) {
            --begin; ++end;
        }
        return make_pair(begin, end);
    }
};

• #dp