Edward on Java with Leetcode: 5. Longest Palindromic Substring

Photo by Andrew Palmer on Unsplash

Problem

Problem description is available at 5. Longest Palindromic Substring

Algorithm

I have an algorithm using DP (dynamic programming) here. But here I’m going to save some brain cells using a more straightforward way.

By palindrome definition, it should either center a char in the string or center a char and its precedent char (if they are the same), and then extend its wings from 2 different directions. That makes a perfect forloop.

Java Solution

Codes look like below.

class Solution {
    public String longestPalindrome(String s) {
        /*
        For each charactor, it can be the center chararactor of a palindrome
        or as the right side (except the first one) of a palindrome.
        */
        String longest = "";
        int len = s.length();
        for (int i = 0; i < len; i++){
            int wing = 0;
            while(i - wing >= 0 && i + wing < len){
                if (s.charAt(i - wing) != s.charAt(i + wing)) {                    
                    break;
                }
                if (wing * 2 + 1 > longest.length()) 
                    longest = s.substring(i - wing, i + wing + 1);
                wing++;
            }        

            if ( i == 0 ) continue;

            int j = i - 1;
            wing = 0;
            while(j - wing >= 0 && i + wing < len){
                if (s.charAt(j - wing) != s.charAt(i + wing)) {                    
                    break;
                }
                if (wing * 2 + 2 > longest.length())0
                    longest = s.substring(j - wing, i + wing + 1);
                wing++;
            }            
        }
        return longest;
    }
}

Java Knowledge

1. Java String’s substring function.

Syntax

public String substring(int begIndex, int endIndex);

Parameters

• beginIndex : the begin index, inclusive.
• endIndex : the end index, exclusive.

2. In case of printing debug information, below code can be used.

System.out.println(aVariable);

If I want to print more than 1 integers in the same row

System.out.println(aInt + "" + bInt);