How to find the longest palindromic substring in Java?

In this blog we are going to solve the problem of finding the longest palindromic substring. We will begin our journey by understanding the theory behind it and then, guided by examples, we will a take a detailed look at the approach to the solution.Finally,we will write the code in Java. Every corner condition in the code will be explained with appropriate examples so that you get a complete understanding of the code.

Understanding the meaning of longest palindromic substring

The input that is given to us is a string and we need to find the longest palindromic substring. Let’s break this down a little bit.

A substring is part of a string, a continuous sequence of characters in a string. If the input string is “abracadabra”, every single character is a substring. Strings like “ab”,”br”, “da”,”ra”, “abr”,”dabra” etc are all substrings. What is not a substring is “dbra” since it is not a continuous sequence of characters(‘a’ is missing) in abracadabra.

A palindrome is a word, phrase or a sequence of characters that reads the same backward as forward. Some examples of palindromes are kayak, rotor, or the names Hannah and Ava. You read it in the forward or backward direction and you get the same sequence of characters. Having understood the meaning of a substring and a palindrome, let’s understand the meaning of a palindromic substring.

In abracadabra, the highlighted string, “aca”, is a substring. It is also a palindrome and hence a palindromic substring. Another example is the substring,abba, in the string, dabba. By the way, dabba is an Indian-style tiffin box. Having understood the meaning of palindromic substring,we are left with finding the longest among them. Let’s jump on to an example right away.

As you can see in the above string, 3 palindromes have been highlighted. The first one, shown in red color is “ABA”, it has a length of 3. Then we have the palindromic substring, “ABCDEDCBA”, which is of length 9. Finally, we have the 3rd palindromic substring, “1234567887654321” which has a length of 16, which is the largest palindromic substring. With this understanding, let’s go ahead and analyse the approach to solve this problem.

Logical and technical analysis of the solution

A palindrome reads the same forwards as backwards. Let’s consider the strings rotor, dabba, bob and otto. Other than the fact that they are palindromes, what do you see?

A very important observation is the fact that the center of a palindrome is either :

1. A single character in the middle and the rest of characters are a mirror image on either side of that character.
2. Two similar characters in the middle and then the rest of the characters are mirror images.

Given a string, we can look at it and then decide if it is case one or case two. But from the perspective of writing code, we will need to handle these 2 cases. I urge you to read and understand these 2 cases again since it is a very important factor to understand the solution from a theoretical and technical point of view.

This can occur anywhere in the string, it could be the first few characters in the string, it could be the last few characters, in the middle or elsewhere.

A quick overview of indexes in a string

The index in a string starts from 0. If the total length of the string is ‘n’, the index ends at n-1. I know you already knew this but a quick refresher always helps.

In every image and example so far, have you observed a dotted box around the center of the palindrome? It’s either a single character or 2 similar characters. I want you to imagine the case with 2 similar characters in the middle as a single one. Just remember this, we will revisit this soon. Now, let’s look at the procedure to get to the solution considering the 2 cases about the center of the character.

Logical steps to get to the answer

We know that around the center of a string, which is a palindrome, the characters on the left and right must be a mirror image. If they are not, it is not a palindrome.

General procedure

We assume that each character in a string is a central point of a potential palindrome. With that as our reference, we compare the character on the left side with the right side. If they are equal, we continue checking by moving further towards the left and right. If they are unequal, we move to next character which will again be considered as a potential central reference.We need to keep on repeating this procedure until we reach the end of the string. At each step, if we find a potential palindrome, we need to maintain the length so that at the end of it , we can find out the one with maximum length. This will be the overall procedure.

The case of two characters in the middle

Do you remember the 2 scenarios about the character(s) at the center ? The first case has a single character in the middle. The 2nd case has 2 characters in the middle and here, the characters will be next to each other. How do we decide which one to take ?

For every character under consideration, we check for a palindrome considering both cases but take the maximum length of the two. Remember, we can visually see and determine it, but both cases needs to be dealt with in the code. These 2 cases need to be part of the general procedure described earlier.

A visual representation of the procedure

Notice that for each index, we are checking the two cases and then moving to the next character. The execution continues below for i = 2.

Some of the important things to notice about this procedure are the following:

1. We iterate through the string only once.
2. When we move the towards the left and the right after considering a center point, we need to ensure that we don’t move towards the left, beyond the first character and the same holds true for the movement towards the right.
3. Towards the end of the procedure, we are able to find out the maximum length of a palindromic substring, but we need to also find out what that substring is. In the above case, it is “abba”. To do this, we will need to maintain the starting and ending indices of a substring whose length is maximum at any given point in the procedure.

Technical analysis to arrive at the complete code

We need to fix or assume each character as the center point and start exploring towards the left hand side and right hand side to check if it is a palindrome. I know I am kind of reminding you again, but consider the 2 cases – single character as center and 2 characters at the center. We need to find the maximum among the two.

Iterating ‘n’ times where ‘n’ is the length of the string

Let’s name the method which checks for the matching characters on the left and right as “exploreFromCenter”. This method will keep checking if the characters on the left and right of that middle point are the same and return the length of the palindrome.

for (int i = 0; i < s.length(); i++) {
    int lengthSingleCharacter = exploreFromCenter(s, i, i);
    int lengthTwoCharacters = exploreFromCenter(s, i, i + 1);
    int length = Math.max(lengthSingleCharacter, lengthTwoCharacters);
}

A ‘for’ loop is required to consider each character as the middle point. We call the method, exploreFromCenter, which returns the length of the palindrome. It is called twice for the 2 cases. The first time, it is called with ‘i’ and the second time with ‘i+1’. Note that we are not changing the value of ‘i’ in this step.

Code for exploring around the central character

private static int exploreFromCenter(String s, int left, int right) {

        if (s == null || left > right)
            return 0;

        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }

        return right - left - 1;
}

1. Other than the input string, the input to this method is the index of the single character or indices of 2 characters, current index and the next one.
2. Since we are moving towards the left and right by one, we decrement left index by one and increment right index by one. But, we cannot move the left and right index endlessly, can we ? We move only upto the first character, hence the condition left>=0. We can move the right pointer upto the last character and hence the condition, right < s.length(). Note, it is < than and not <= since we want to move upto the last character, strings begin from index 0.
3. The last line of code, right – left – 1 , which returns the length of palindromic substring needs a bit of explanation. I hope the image below will give you a good idea about the same.

Code for maintaining the largest length of the palindromic substring

We started writing the code with the ‘for’ loop which handled the 2 cases and found the maximum length among those 2 cases. But this happens for every character in the string. We also need to maintain the maximum length among all the substrings that we have found so far. How can we do that when the method, ‘exploreFromCenter’, returns only the length ?

We need to maintain the start and end index of each palindromic substring we have found so far. This start and end index will point to the first and last character of the palindromic string. Each time we find a bigger palindrome, we update/reset the start and end indices.The final positions of the start and end indices should give us a reference to the actual substring. Let’s expand our initial code further to incorporate this logic-

private static String findLongestPalindromicSubString(String s) {

        if (s == null || s.trim().length() == 0) return "";

        int start = 0;
        int end = 0;

        for (int i = 0; i < s.length(); i++) {
            int lengthSingleCharacter = exploreFromCenter(s, i, i);
            int lengthTwoCharacters = exploreFromCenter(s, i, i + 1);

            int length = Math.max(lengthSingleCharacter, lengthTwoCharacters);
          

            if (length > end - start + 1) {
                start = i - ((length - 1) / 2); //length -1 for even length strings
                end = i + (length / 2);
            }
        }
        return s.substring(start, end + 1);
}

We have initialized the start and end indices to zero on lines 5 and 6. Later, we reset and maintain the indices to the largest palindrome. Remember, once the middle character is fixed, the left and the right index equally move by 1 until matching characters are found. This should give you an insight into lines 16 and 17.

Why does the start index subtract 1 from the length but end index does not ?

Since we have moved equally towards the left and the right and we have a reference to the center, we think that the total length divided by 2 will give us the actual result. But it does not, let’s go ahead and understand the reason behind this.

When the input is “rotor” and i = 2, the 1st case where the single character is in the middle returns a palindromic length of 5. We need to find the start and end indices based on this. We do that with the help of the fact that i = 2 and we have moved equally towards the left and right. How do we get to the character ‘r’ on the left side in ‘rotor’ based on i = 2 and length = 5? We need to subtract something from ‘i’ and with the same logic, add something to ‘i ‘ to reach ‘r’ on the right side. Using this logic, if we were to do the following, we think we have the right result.

start = i - (length / 2);
end = i + (length / 2);

This seems to work. Since the length is 5, length /2 gives us 2. The value of i is also 2. So, 2 -(5/ 2) is equal to 0, this is where we want our start index pointer. The end index is calculated as 2 + (5/2) which gives us 4. Note that the length of the palindromic substring is 5 and it has a single character in the middle.

But let’s consider another example now, the one which we have been looking at for a long time now, dabba, which is making me a little hungry now ! But hold on, we are almost there, let’s understand this and then go and get our dabba.

The value of the start index is calculated as i – (length/2) which gives us 2 – ( 4/2) = 0. This will take the start index to 0. This is an incorrect result. The end index is calculated as i + (length/2), which is 2 + (4/2) = 4, this is where we want our end index to point to. To fix the logic for the start index, we need to subtract one from the length and then divide by 2.

start = i - ((length - 1) / 2);
end = i + (length / 2);

With this fix, start index will be 2-((4-1)/2) = 2 -(3/2) = (2 -1) = 1. This needs to be done for palindromes which are of even length and the fact that there are really two characters virtually considered as one in the middle.This needs to be adjusted in the total length. When i =2, we executed a call to the function,exploreFromCenter, but we sent the value of i and i+1.

The last line which makes a call to the substring function has end +1 as the 2nd parameter. This is done because the function,substring, returns all characters before that index, it does not include the character at the index specified as the second parameter.

Complete code

package ds;

public class LongestPalindromicSubstring {

    private static String findLongestPalindromicSubString(String s) {

        if (s == null || s.trim().length() == 0) return "";

        int start = 0;
        int end = 0;

        for (int i = 0; i < s.length(); i++) {
            int lengthSingleCharacter = exploreFromCenter(s, i, i); // Single character in the middle.
            int lengthTwoCharacters = exploreFromCenter(s, i, i + 1); //Two characters in the middle .

            int length = Math.max(lengthSingleCharacter, lengthTwoCharacters);
         

            if (length > end - start + 1) {
                start = i - ((length - 1) / 2);
                end = i + (length / 2);
            }
        }
        return s.substring(start, end + 1);
    }

    private static int exploreFromCenter(String s, int left, int right) {

        if (s == null || left > right)
            return 0;

        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }

        return right - left - 1;
    }

    public static void main(String[] args) {
        String answer = findLongestPalindromicSubString("HYTBCABADEFGHABCDEDCBAGHTFYW1234567887654321ZWETYGDE");
        System.out.println(answer);
    }

}

Conclusion

We were able to solve this problem with an overall time complexity of O(n²). We used a single ‘for ‘ loop but for each character we had to compare, move indices around to find the maximum length of the palindromic substring. Overall, the code is not difficult but there are some corner cases, adjustments which we had to handle in the code and these cases can be difficult to understand without going through multiple examples.

I hope you have not only got an answer to the ‘how’ parts of the solution but also the ‘why’ parts of it. Just remember the two cases about the single character or two characters in the middle and you will definitely be able to come up with the code.

Can we improve the time complexity ? Yes, we can ! This can be done using Manacher’s algorithm. But right now, I am definitely going to grab my ‘dabba’ , what about you ?