> For the complete documentation index, see [llms.txt](https://emmaguo100.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://emmaguo100.gitbook.io/leetcode/02-01-2022-5.md).

# 02/01/2022 5

Method 1:

brutal force, check all the substrings and if they are palindrome, and then find the one with the max length. 

Time O(n^3)

Space O(1)

```
    class Solution { 
    public String longestPalindrome(String s) { 
    //brutal force 
    int len = s.length(); 
    if(len < 2) return s;
    
    int maxLen = 1;
    int begin = 0;
    char[] charArray = s.toCharArray();
    
    for(int i = 0; i < len -1; i++){
        for(int j = i + 1; j < len; j++){
            if(j - i + 1 > maxLen && validPalindrome(charArray, i, j)){
                maxLen = j - i + 1;
                begin = i;
            }
        }
    }

    return s.substring(begin, begin + maxLen);
}
private boolean validPalindrome(char[] charArray, int left, int right){
    while(left < right){
        if(charArray[left] != charArray[right]) return false;
        left++;
        right--;
    }
    return true;
}
```

}

Method 2:&#x20;

Extend from the center to the ends. For each index i or (i, i+1), we take it as middle elements and expand towards two ends to find the longest palindrome.

Time O(n^2)

Space O(1)

```
   class Solution { 
   public String longestPalindrome(String s) { 
   // extend from the middle 
   int len = s.length(); 
   if(len < 2) return s; 
   int maxLen = 1; int begin = 0; 
   char[] charArray = s.toCharArray(); 
   for (int i = 0; i < len -1; i++){ 
       int oddLen = expand(charArray, i, i); 
       int evenLen = expand(charArray, i, i + 1); 
    
        int curMaxLen = Math.max(oddLen, evenLen);
        if(curMaxLen > maxLen){
            maxLen = curMaxLen;
            begin = i - (maxLen - 1)/2;
        }
 }
 return s.substring(begin, begin + maxLen);
}  
private int expand(char[] charArray, int left, int right){
    int len = charArray.length;
    while(left >= 0 && right < len){
        if(charArray[left] == charArray[right]){
            left--;
            right++;
        }else{
            break;
        }
    }
    //right - left + 1 -2 = right -left -1. excluding i and j position
    return right - left -1;
}
```

}

Method 3: Dynamic Programming

if dp\[l +1]\[r - 1] is true and s\[l] == s\[r], then dp\[l]\[r] is True also.

Time O(n^2)

Space O(n)

```
class Solution { 
public String longestPalindrome(String s) { 
//Dynamic Programming 
int len = s.length(); 
if(len < 2) return s;

int maxLen = 1;
int begin = 0;

//dp[i][j] means if s[i..j] is palindrome 
boolean [][] dp = new boolean[len][len];
for(int i = 0; i < len; i++) dp[i][i] = true;

char[] charArray = s.toCharArray();
for (int j = 1; j < len; j++){
    for (int i = 0; i < j ; i++){
        if(charArray[i] != charArray[j]){
            dp[i][j] = false;
        }else{
            if(j - i < 3){
                dp[i][j] = true;
            }else{
                dp[i][j] = dp[i + 1][j - 1];
            }
        }
        if(dp[i][j] && j - i + 1 > maxLen){
            maxLen = j - i + 1;
            begin = i;
        }
    }
 }
 return s.substring(begin, begin + maxLen);
}
```

}