README.md

5. Longest Palindromic Substring (Medium)

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

Solution 1.

// Problem: https://leetcode.com/problems/longest-palindromic-substring/
// Author: github.com/ankuralld5999
// 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);
    }
};