Algorithm- Longest Palindromic Substring

Description

Given a string s, return the longest palindromic substring in s.

Example

Example :

Input: s = “babad”

Output: “bab”

Explanation:

“aba” can also be a valid answer.

Constraints

• 1 <= s.length <= 1000
• s consist of only digits and English letters.

Approach

The solution will be given in Java. The algorithm will be discussed step by step.

Java implementation

public String longestPulindromicSubstring(String s){
        if (s == null || s.isEmpty())
            return "";
        int start = 0, end = 0;
        for (int i = 0;  i < s.length(); i++){
            int len1 = expandAroundCenter(s, i, i);
            int len2 = expandAroundCenter(s, i, i + 1);

            int len = Math.max(len1, len2);
            if (len > end - start){
                start = i -(len -1 ) / 2;
                end = i + len/2;
            }
        }
        return s.substring(start, end + 1);
    }

    private int expandAroundCenter(String s, int left, int right){
        int L = left, R = right;

        while (L >= 0 && R < s.length() && s.charAt(L) == s.charAt(R)){
            L--;
            R++;
        }
        return R - L - 1;
    }

Discussion

1. The longestPalindrome function takes a string s as input.
2. It first checks if the string is null or empty. If it is, it immediately returns an empty string, as there can be no palindrome in an empty or null string.
3. The two variables, start and end, are initialized to keep track of the indices of the longest palindrome substring found so far, and initially, they are set to 0.
4. The algorithm enters a loop that iterates through each character in the string s. The loop uses an index variable i that starts from 0 and goes up to s.length() - 1.
5. For each character at index i, the algorithm calls the expandAroundCenter function twice to find palindromes centered at the current character or between the current character and the next character.
6. The expandAroundCenter function takes three parameters: the string s, the left index (i), and the right index (i or i + 1 depending on the case). It uses these indices to expand outward from the center, checking if the characters at the left and right indices are equal. The function continues expanding as long as the characters match and also as long as the indices are within the bounds of the string.
7. The expandAroundCenter function returns the length of the palindrome found by subtracting the right index from the left index and subtracting 1. An example is , if the palindrome length is 5, the difference between the indices would be 4.
8. Back in the longestPalindrome function, the algorithm calculates the maximum length of the palindromes found by taking the maximum between the lengths obtained from the two calls to expandAroundCenter.
9. If the length of the current palindrome is greater than the length of the previously recorded longest palindrome (end-start), the algorithm updates the start and end indices to reflect the new longest palindrome.
10. After the loop finishes iterating through all characters in the string, the function returns the substring of s that corresponds to the longest palindrome, using the start and end indices.

Check out my other article or Algorithm – Reverse words in a string here

Our Facebook page is here. You can also find our Youtube channel here.