Good day! Hope your day has started on the right note. The days are getting shorter. Every morning after breakfast my wife and I head out for a 2.5 mile walk. We are leaving home a few minutes before 07:00 AM because earlier is dark. We prefer walking with day light.
Today’s problem is LeetCode 5 Longest Palindromic Substring. Before attempting to solve the problem we need to know what a palindrome is.
Now that we understand the concept of a palindrome we are prepared to read the requirements for this problem:
Given a string s, return the longest palindromic substring in s. Constraints: o 1 <= s.length <= 1000 o s consist of only digits and English letters. Hints: o How can we reuse a previously computed palindrome to compute a larger palindrome? o If “aba” is a palindrome, is “xabax” a palindrome? Similarly is “xabay” a palindrome? o Complexity based hint: If we use brute-force and check whether for every start and end position a substring is a palindrome we have O(n^2) start - end pairs and O(n) palindromic checks. Can we reduce the time for palindromic checks to O(1) by reusing some previous computation.
The requirements are quite simple. We are given a text string and we are required to find the longest palindrome in it. If more than one palindrome with the same length is found, we may return any of them.
We will attempt to solve this problem using the Java programming language using the VSCode IDE on a Windows 10 computer. I am still watching and experimenting with the Python on-line tutorial. When done I will switch languages to Python in this blog. Until then, it is going to be Java.
There is a well know algorithm to find the longest palindrome substring. You can read about it here. If you are interested in an implementation in Java you can find it here.
Since I will be solving the problem in one of my computers, I will not be using the IDE provided by LeetCode. Since I am not using the LeetCode IDE I will have to write a test scaffold that reads the input string, calls the function of interest and displays the output.
babad main <<< s ==>babad<== longestPalindrome <<< i: 0 palindrome ==>b<== longestPalindrome <<< i: 1 palindrome ==>bab<== longestPalindrome <<< i: 2 palindrome ==>aba<== main <<< output ==>aba<== Note: "aba" is also a valid answer. cbbd main <<< s ==>cbbd<== longestPalindrome <<< i: 0 palindrome ==>c<== longestPalindrome <<< i: 1 palindrome ==>bb<== main <<< output ==>bb<== main <<< s ==><== main <<< output ==><== a main <<< output ==>a<== ac main <<< output ==>c<== 12345678aab main <<< output ==>aa<== baa12345678 main <<< output ==>aa<== bananas main <<< output ==>anana<== main <<< s ==>bananas<== longestPalindrome <<< i: 0 palindrome ==>b<== longestPalindrome <<< i: 1 palindrome ==>a<== longestPalindrome <<< i: 2 palindrome ==>ana<== longestPalindrome <<< i: 3 palindrome ==>anana<== main <<< output ==>anana<== banana main <<< output ==>anana<== abracadabra main <<< s ==>abracadabra<== longestPalindrome <<< i: 0 palindrome ==>a<== longestPalindrome <<< i: 1 palindrome ==>b<== longestPalindrome <<< i: 2 palindrome ==>r<== longestPalindrome <<< i: 3 palindrome ==>a<== longestPalindrome <<< i: 4 palindrome ==>aca<== longestPalindrome <<< i: 6 palindrome ==>ada<== main <<< output ==>ada<==
I tested the code against all the provided examples. I also added a few more while reading some articles on-line.
Please note that some examples display some debugging statements. Such statements are not part of the solution. They are used to better understand how the solution operates.
Our test code reads the input string. It then calls the function of interest. The resulting palindrome is then displayed.
public String longestPalindrome(String s) {
}
This is the signature of the function of interest. It expects the input string and should return the longest palindrome found.
/**
* Test scaffold.
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// **** open a buffered reader ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// **** read string ****
String s = br.readLine().trim();
// **** close the buffered reader ****
br.close();
// ???? ????
System.out.println("main <<< s ==>" + s + "<==");
// **** compute and display longest palindromic substring ****
System.out.println("main <<< output ==>" + longestPalindrome(s) + "<==");
}
Our test scaffold opens a buffered reader. It then reads the input string. The buffered reader is closed. We finally call the function of interest and displayed the longest palindrome found in the specified string.
/**
* Given a string s, return the longest palindromic substring in s.
* Execution: O(n^2) and space: O(1)
*
* 177 / 177 test cases passed.
* Status: Accepted
* Runtime: 24 ms
* Memory Usage: 39 MB
*/
static String longestPalindrome(String s) {
// **** sanity check(s) ****
if (s != null && s.length() <= 1) return s;
// **** initialization ****
int start = 0;
int end = 0;
int len = 0;
int len1 = 0;
int len2 = 0;
// **** traverse the string left to right - O(n) ****
for (int i = 0; i < s.length(); i++) {
// **** single character at center (odd number of characters in s) - O(n)****
len1 = expandFromHere(s, i, i);
// **** contiguous characters at center (even number of characters in s) - O(n) ****
len2 = expandFromHere(s, i, i + 1);
// **** select the max length for the palindrome ****
len = Math.max(len1, len2);
// **** update the start and end characters in the palindrome (if needed) ****
if (len > end - start) {
// **** update start and end indices in palindrome ****
start = i - (len - 1) / 2;
end = i + (len / 2);
// ???? ????
System.out.println("longestPalindrome <<< i: " + i + " palindrome ==>" + s.substring(start, end + 1) + "<==");
}
}
// **** return the longest palindrome ****
return s.substring(start, end + 1);
}
We start by performing some sanity checks.
A set of variables are then initialized. Their use will become obvious as we continue looking at the code.
We encounter a loop that traverses the string left to right.
For each character we determine the longest palindrome based on it and place the length in a variable. The same operation is repeated but this time we use the two consecutive characters. This is done due to the fact that some strings have odd character counts while others have even. Please take a look at the samples to verify such fact.
Once we have both lengths, we select the longest.
If the length is larger than the previous one expressed as a start and end index, we update the start and end indices.
When all is said and done we return the substring holding the longest palindrome found in the string.
/**
* Auxiliary function.
* Looks for palindromes starting at the specified range.
* O(n)
*/
static private int expandFromHere(String s, int left, int right) {
// **** sanity check(s) ****
if (s == null || left > right) return 0;
// **** expand the palindrome range as far as possible ****
while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
left--; right++;
}
// **** length of palindrome ****
return right - left - 1;
}
This is the auxiliary function we use to determine the length of a palindrome given the left and right indices in the string.
In a nutshell, we loop while the end characters are the same. On each pass we move the left index left and the right index right.
When all is done, we return the length of the palindrome we found using the specified indices.
Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository.
Please note that the code here presented might not be the best possible solution. In most cases, after solving the problem, you can take a look at the best accepted solution provided by the different web sites (i.e., HackerRank, LeetCode).
If you have comments or questions regarding this, or any other post in this blog, please do not hesitate and leave me a note below. I will reply as soon as possible.
Keep on reading and experimenting. It is one of the best ways to learn, become proficient, refresh your knowledge and enhance your developer toolset.
Thanks for reading this post, feel free to connect with me John Canessa at LinkedIn.
Regards;
John