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

1. 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.
2. For each character i in the input string s, check for even and odd length palindromes using two while loops.
3. 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.
4. In the odd length case, set l=i-1 and r=i+1, and repeat the same process as in the even length case.
5. If no palindromic substring is found, return the first character of the input string as the longest palindromic substring.
6. 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