Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
Example 1:
Input: "babad" Output: "bab" Note: "aba" is also a valid answer.
Example 2:
Input: "cbbd" Output: "bb"
Companies:
Amazon, Microsoft, Facebook, Google, Apple, Adobe, Yahoo, Bloomberg, Uber, Pure Storage, eBay, Alibaba, LinkedIn, Cisco, NetEase, Oracle, Roblox
// OJ: https://leetcode.com/problems/longest-palindromic-substring/
// Author: github.com/lzl124631x
// Time: O(N^2)
// Space: O(1)
class Solution {
private:
int expand(string &s, int L, int R) {
while (L >= 0 && R < s.size() && s[L] == s[R]) {
--L;
++R;
}
return R - L - 1;
}
public:
string longestPalindrome(string s) {
if (s.empty()) return s;
int start = 0, maxLen = 0;
for (int i = 0; i < s.size(); ++i) {
int len1 = expand(s, i, i);
int len2 = expand(s, i, i + 1);
int len = max(len1, len2);
if (len > maxLen) {
start = i - (len - 1) / 2;
maxLen = len;
}
}
return s.substr(start, maxLen);
}
};