LEETCODE 0005

QUERY:5. Longest Palindromic Substring
Given a string s, return the longest palindromic substring in s.

example1:
Input: s = “babad”
Output: “bab”
Explanation: “aba” is also a valid answer.

PYTHON

DP design
class Solution:
## s = input string
## n = len(s)
## res = result = target palindromic str
def longestPalindrome(self, s: str) -> str:
res = ''
    for i in range(len(s)):
        for j in range(len(s), i, -1): ## start, end, step
            if len(res) >= (j - i):
                break
            if s[i:j] == s[i:j][::-1]:
                res = s[i:j]
                break
    return res

JAVA

## JKB
class Solution {
int maxLen = 0;
int start = 0;
public String longestPalindrome(String s) {
    for(int i = 0; i < s.length(); i++){
        helper(i, i, s);
        helper(i, i + 1, s);
    }

    return s.substring(start, start + maxLen);
}

private void helper(int left, int right, String s){
    while(left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)){
        if(right - left + 1 > maxLen){
            start = left;
            maxLen = right - left + 1;
        }
        left--;
        right++;
    }
}

}

C++:

JKB

// Author: Huahua, 16 ms, 8.7 MB
class Solution {
public:
string longestPalindrome(string s) {
const int n = s.length();
auto getLen = [&](int l, int r) {
while (l >= 0 && r < n && s[l] == s[r]) { –l; ++r; } return r – l – 1; }; int len = 0; int start = 0; for (int i = 0; i < n; ++i) { int cur = max(getLen(i, i), getLen(i, i + 1)); if (cur > len) {
len = cur;
start = i – (len – 1) / 2;
}
}
return s.substr(start, len);
}
};