Longest Palindromic Substring Companies Given a string s, return the longest palindromic substring in s. Solution in C++

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

Example 1: Input: s = “babad” Output: “bab”

Explanation: “aba” is also a valid answer.

Example 2: Input: s = “cbbd” Output: “bb”

Constraints:

  • 1 <= s.length <= 1000
  • s consist of only digits and English letters.
class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size();
    if (n < 2) return s;
    int start = 0, maxLen = 1;
    for (int i = 0; i < n; ) {
        if (n - i <= maxLen / 2) break;
        int left = i, right = i;
        while (right < n - 1 && s[right + 1] == s[right]) ++right;
        i = right + 1;
        while (right < n - 1 && left > 0 && s[right + 1] == s[left - 1]) {
            ++right;
            --left;
        }
        int len = right - left + 1;
        if (len > maxLen) {
            start = left;
            maxLen = len;
        }
    }
    return s.substr(start, maxLen);
    }
};

Leave a Comment