# Longest Palindromic Substring 5

###### tags: `leetcode`,`dp`,`recursion`,`medium`

>ref: https://leetcode.com/problems/longest-palindromic-substring/
>
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.

>1. dp init cond: count[i][i]=true; count[i][i+1]= s[i]==s[i+1] ex."aa","bb"
>2. if s[i]==s[j] then count[i][j]=count[i+1][j-1]
>3. timeCom:O(MN) spatialCom:O(MN)

    public String longestPalindrome(String s) {
        
        byte[] b=s.getBytes();
        
        int max=0;
        int x=0;
        int y=0;
        
        boolean[][] count= new boolean[b.length][b.length];
        
        for(int i=b.length-1; i>=0;i--){
            
            count[i][i]=true;
            for(int j=i+1;j<b.length;j++){
                
                if(b[i]==b[j]){
                    if(j-i==1 || count[i+1][j-1] ){
                        count[i][j]=true;
                    }
                    if(count[i][j] && j-i>y-x){
                        x=i;
                        y=j;
                    }
                }
            }
            
        }
        
        return s.substring(x,y+1);
        
        
    }

>1. recursive call, len1 consider odd number substring, len2 as even number substring.
>2. timeCom:O(MN) spatialCom:O(1)(ignore the recusive call variable)

    int st,end;
    
    public String longestPalindrome(String s) {
        
        if(s.length()<2)return s;
        
        for(int i=0;i<s.length();i++){

            int len1=helper(s,i,i);
            
            int len2=helper(s,i,i+1);
            
            int max= Math.max(len1,len2);
            
            if(max> end-st){
                st= i- (max-1)/2;
                end= i+(max)/2;
            
            }
        }
        return s.substring(st,end+1);
    }
    
    
    public int helper(String s, int start,int end){
        
        if(start>end)return 0;
        
        while(start>=0 && end<s.length() && s.charAt(start)==s.charAt(end)){
            start--;
            end++;
        }
        return end-start-1;
        
    }