# 5. Longest Palindromic Substring (Medium)

https://leetcode.com/problems/longest-palindromic-substring/

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"
```

## Solutions

``````class Solution {

// Initially, set all the single char as palindrome, then extend out to both sides by one slot every lap.

public String longestPalindrome(String s) {
if (s == null || s.length() == 0) {
return "";
}

int len = s.length();

// keep track of the palindromes
boolean[][] isPal = new boolean[len][len];

int ans = 0;
int startIndex = -1;

// operations for range =1, =2 and >2 are different, three situations
// must be dealt with respectively
for (int range = 1; range <= len; range++) {

// when range length is 1
for (int i = 0, j = 0; i < len && range == 1; i++, j++) {
isPal[i][i] = true;
ans = 1;
startIndex = i;
}

// when range length is 2
for (int i = 0, j = i + 1; j < len && range == 2; i++, j++) {
if (s.charAt(i) != s.charAt(j)) {
continue;
}

isPal[i][j] = true;
ans = 2;
startIndex = i;
}

// when range length > 2
for (int i = 0, j = range - 1; j < len && range > 2; i++, j++) {
if (s.charAt(i) != s.charAt(j)) {
continue;
}

// expand the range of the substring to both sides by one step
// if A[i+1][j-1] is palindromic, so is A[i][j], vice versa
isPal[i][j] = isPal[i + 1][j - 1];

// if A[i][j] is palindromic and longer than previous one,
// update the max length with the new value
if (isPal[i][j] && range > ans) {
ans = range;
startIndex = i;
}
}
}

return s.substring(startIndex, startIndex + ans);
}
}
``````