Solving LeetCode “5. Longest Palindromic Substring” using Dynamic Programming

Type: Medium

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

Example 1:
Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.

Example 2:
Input: s = "cbbd"
Output: "bb"

Constraints:

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

Approach:

Initialization:
The code initializes two private integer variables, start and length, to keep track of the starting index and length of the longest palindromic substring found. Initially, both are set to 0.

longestPalindrome Method:
A public method named longestPalindrome is defined, which takes a single argument, the input string s, and returns the longest palindromic substring found.

Edge Case Check:
The method first checks if the length of the input string s is 0 or 1. If it's either of these cases, it directly returns the string itself because a single character or an empty string is considered a palindrome.

Iteration through the String:
A for loop iterates through the characters of the string s. The variable i represents the current center of the potential palindrome.

Palindrome Checking:
Inside the loop, the code calls the palindromeChecker method twice:
First, it calls palindromeChecker(i, i, s) to check for odd-length palindromes, where i is the center character.
Then, it calls palindromeChecker(i, i + 1, s) to check for even-length palindromes, where i and i + 1 represent the two center characters for even-length palindromes.

palindromeChecker Method:
This private method is responsible for checking if a given pair of pointers (left and right pointers) can form a palindrome when expanded around the center.
It uses a while loop to check if the characters at leftPointer and rightPointer are the same and if the pointers are within the bounds of the string.
If they are the same, it means the palindrome can be extended, so leftPointer moves one step to the left (decremented) and rightPointer moves one step to the right (incremented).

Updating the Longest Palindrome:

After the while loop exits, it means the palindrome expansion has stopped either because leftPointer has gone too far to the left, rightPointer has gone too far to the right, or a character mismatch has been found.

The method then checks if the length of the current palindrome (found from leftPointer to rightPointer) is greater than the length of the previously recorded longest palindrome (length variable).
If it's longer, it updates start to leftPointer + 1 (the start index of the current palindrome) and length to rightPointer - leftPointer - 1 (the length of the current palindrome).

Returning the Result:
After processing all potential centers in the string, the longestPalindrome method returns the longest palindromic substring found by using the substring() method with the start and start + length indices.
In summary, this code efficiently finds the longest palindromic substring in a given string by using a center-expansion approach. It maintains start and length variables to keep track of the longest palindrome found during the process. The approach ensures that all possible palindromes are checked, and the longest one is returned as the result.

Code:

public class Solution {
    private int start = 0;
    private int length = 0;
    public String longestPalindrome(String s) {
        if (s.length() == 1 || s.length() == 0)
            return s;

        for (int i = 0; i < s.length() - 1; i++) {
            palindromeChecker(i, i, s);
            palindromeChecker(i, i + 1, s);
        }

        return s.substring(start, start + length);
    }

    private void palindromeChecker(int leftPointer, int rightPointer, String s) {
        while (leftPointer >= 0 && rightPointer < s.length() && s.charAt(leftPointer) == s.charAt(rightPointer)) {
            leftPointer--;
            rightPointer++;
        }
        if (length < rightPointer - leftPointer - 1) {
            start = leftPointer + 1;
            length = rightPointer - leftPointer - 1;
        }
    }
}

Happy coding,
shiva