# Longest Palindromic Substring

In this problem, we have to find the longest palindromic substring and return it.

A substring is a contiguous sequence of characters within a string. The term "longest palindrome substring" refers to a continuous substring of a given string that is a palindrome, or one that reads the same both forward and backward. For instance, the words "racecar" and its substrings "cec" and "aceca" all contain palindromes. The longest palindromic substring is "aceca".

#### Approach

We will solve this problem using 'Expand Around Center' approach. This approach is a simple and efficient way to find the longest palindromic substring within a given string. The main idea is to treat each character in the string as a potential center of a palindrome and then expand outward to check for symmetry.

#### Algorithm

- Initialize the variables l and r used for checking palindrome. subStr is used for storing the resulting substring and maxLen is used to store the length of the longest palindromic substring.
- For each character i in the input string s, check for even and odd length palindromes using two while loops.
- In the even length case, set l=i and r=i+1, and check if the substring s[l:r+1] is a palindrome. If it is, update the subStr variable and the maxLen variable if the length of the substring is greater than the current maxLen. Then, expand the palindrome by incrementing l to the left and r to the right, and continue checking for palindromes until the substring is no longer a palindrome.
- In the odd length case, set l=i-1 and r=i+1, and repeat the same process as in the even length case.
- If no palindromic substring is found, return the first character of the input string as the longest palindromic substring.
- Otherwise, return the subStr variable, which stores the longest palindromic substring found.

#### Complexity

- Time Complexity: O(n^2), where n is the size of the array
- Space Complexity: O(1), where n is the size of the array

##### Java Code

```
public class LongestPalindromicSubstring {
public String longestPalindrome(String s) {
int left, right;
int maxLen = 0;
int start = 0, end = 0;
for (int i = 0; i < s.length(); i++) {
// even length case
left = i;
right = i + 1;
while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
if (right - left + 1 > maxLen) {
start = left;
end = right;
maxLen = right - left + 1;
}
left--;
right++;
}
// odd length case
left = i - 1;
right = i + 1;
while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
if (right - left + 1 > maxLen) {
start = left;
end = right;
maxLen = right - left + 1;
}
left--;
right++;
}
}
return s.substring(start, end + 1);
}
public static void main(String[] args) {
LongestPalindromicSubstring obj = new LongestPalindromicSubstring();
System.out.println("Longest Palindromic Substring is: " + obj.longestPalindrome("babad"));
}
}
```

##### Output

Longest Palindromic Substring is: bab