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);
}
};