Longest Palindromic Substring

Medium

Python

def longest_palindrome(s):
    res=''
    def expand(l,r):
        while l>=0 and r<len(s) and s[l]==s[r]: l-=1; r+=1
        return s[l+1:r]
    for i in range(len(s)):
        for p in [expand(i,i),expand(i,i+1)]:
            if len(p)>len(res): res=p
    return res

Java

public String longestPalindrome(String s){
    String res="";
    for(int i=0;i<s.length();i++){
        String odd=expand(s,i,i),even=expand(s,i,i+1);
        if(odd.length()>res.length()) res=odd;
        if(even.length()>res.length()) res=even;
    } return res;
}
String expand(String s,int l,int r){
    while(l>=0&&r<s.length()&&s.charAt(l)==s.charAt(r)){l--;r++;}
    return s.substring(l+1,r);
}

Key Insight

Python nested function. Java helper method. Expand-around-center identical.

Python → Java Differences

nested function vs helper method
s[l+1:r] vs substring()
Expand-around-center identical

Python

def longest_palindrome(s):
    res=''
    def expand(l,r):
        while l>=0 and r<len(s) and s[l]==s[r]: l-=1; r+=1
        return s[l+1:r]
    for i in range(len(s)):
        for p in [expand(i,i),expand(i,i+1)]:
            if len(p)>len(res): res=p
    return res

Java

public String longestPalindrome(String s){
    String res="";
    for(int i=0;i<s.length();i++){
        String odd=expand(s,i,i),even=expand(s,i,i+1);
        if(odd.length()>res.length()) res=odd;
        if(even.length()>res.length()) res=even;
    } return res;
}
String expand(String s,int l,int r){
    while(l>=0&&r<s.length()&&s.charAt(l)==s.charAt(r)){l--;r++;}
    return s.substring(l+1,r);
}

Algorithm Steps

1. For each center
2. Expand while match
3. Track longest

← Previous All Strings Next →