PALINDROMIC SEQUENCE CODE

The case of two characters in the middleĭo you remember the 2 scenarios about the character(s) at the center ? The first case has a single character in the middle. 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. 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. If they are equal, we continue checking by moving further towards the left and right. With that as our reference, we compare the character on the left side with the right side. We assume that each character in a string is a central point of a potential palindrome. 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. Now, let’s look at the procedure to get to the solution considering the 2 cases about the center of the character. Just remember this, we will revisit this soon. I want you to imagine the case with 2 similar characters in the middle as a single one. 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. String index starts from 0 and ends at n-1 for a string of length ‘n’ I know you already knew this but a quick refresher always helps. If the total length of the string is ‘n’, the index ends at n-1. 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. 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. But from the perspective of writing code, we will need to handle these 2 cases. Given a string, we can look at it and then decide if it is case one or case two. Two similar characters in the middle and then the rest of the characters are mirror images.A single character in the middle and the rest of characters are a mirror image on either side of that character.Other than the fact that they are palindromes, what do you see? Middle point in any palindromeĪ very important observation is the fact that the center of a palindrome is either : Let’s consider the strings rotor, dabba, bob and otto. Logical and technical analysis of the solutionĪ palindrome reads the same forwards as backwards. With this understanding, let’s go ahead and analyse the approach to solve this problem. Finally, we have the 3rd palindromic substring, “1234567887654321” which has a length of 16, which is the largest palindromic substring. Then we have the palindromic substring, “ABCDEDCBA”, which is of length 9. The first one, shown in red color is “ABA”, it has a length of 3. Multiple palindromic substringsĪs you can see in the above string, 3 palindromes have been highlighted. Having understood the meaning of palindromic substring,we are left with finding the longest among them. By the way, dabba is an Indian-style tiffin box. Another example is the substring,abba, in the string, d abba. It is also a palindrome and hence a palindromic substring. In abr acadabra, the highlighted string, “aca”, is a substring. Having understood the meaning of a substring and a palindrome, let’s understand the meaning of a palindromic substring. You read it in the forward or backward direction and you get the same sequence of characters. Some examples of palindromes are kayak, rotor, or the names Hannah and Ava. What is not a substring is “dbra” since it is not a continuous sequence of characters(‘a’ is missing) in abraca d abra.Ī palindrome is a word, phrase or a sequence of characters that reads the same backward as forward. Strings like “ab”,”br”, “da”,”ra”, “abr”,”dabra” etc are all substrings. If the input string is “abracadabra”, every single character is a substring. Let’s break this down a little bit.Ī substring is part of a string, a continuous sequence of characters in a string. The input that is given to us is a string and we need to find the longest palindromic substring. Understanding the meaning of longest palindromic substring

PALINDROMIC SEQUENCE CODE

Every corner condition in the code will be explained with appropriate examples so that you get a complete understanding of the code. 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. In this blog we are going to solve the problem of finding the longest palindromic substring.

Palindromic sequence