Home Strings Longest Palindromic Substring

# Longest Palindromic Substring

0 comment

Let us suppose that we are given a string ‘str’. You need to find out the longest palindrome as a substring. Note that the elements of the string should be contagious.

Example 1:
Input: "aaebabad"Output: "bab"Note: "aba" is also a valid answer

Example 2:
Input: "cbeereed"Output: "eeree"

##### Terminology:

Palindrome: A palindrome is a type of string that reads the same when reading left to right and right to left. An example of a palindrome can be “level”, “racecar”, “kayak” etc.

Sub-string: A string formed formed using the characters of the string that may or may not contain repetitions.

##### Brute Force Method:

As soon as you see the problem, the most first thought that comes to your mind would be to find all the sub-strings from the given string and keep a track of the longest one that we find. That will eventually land you to the right answer, but the time complexity of such an algorithm would be enormous. There total number of sub-strings would be =\frac{n\ *\ (n\ -\ 1)}{2}

This would cause the complexity to quickly reach O(n^2) and we can check if a string is a palindrome in O(n) time, resulting in a total complexity of O(n^3). This is something we do not want as it will take up a lot of time.

##### Optimized Method:

Let us try to aim for a method with a complexity of )(n^2). The algorithm will look something like:

• Start traversing the string from the first character to the last character.
• For each of the position ‘i’ in the string, find out the largest palindrome having an even length and an odd length. Note that a single letter can also be a palindrome.
• The minimum valid even length would be 2. Eg: “aa”, “cc”, xx”.
• The minimum valid odd length would be 1. Eg: “a”, “v”.
• Hence for each of the character in the string, navigate in both left and right directions till the condition for palindrome is satisfied.
• Keep a track of the largest palindrome encountered so far.
• At the end of this loop, you would have the longest palindrome sub-string.
##### Code:
.wp-block-code {
border: 0;
}

.wp-block-code > div {
overflow: auto;
}

.shcb-language {
border: 0;
clip: rect(1px, 1px, 1px, 1px);
-webkit-clip-path: inset(50%);
clip-path: inset(50%);
height: 1px;
margin: -1px;
overflow: hidden;
position: absolute;
width: 1px;
word-wrap: normal;
word-break: normal;
}

.hljs {
box-sizing: border-box;
}

.hljs.shcb-code-table {
display: table;
width: 100%;
}

.hljs.shcb-code-table > .shcb-loc {
color: inherit;
display: table-row;
width: 100%;
}

.hljs.shcb-code-table .shcb-loc > span {
display: table-cell;
}

.wp-block-code code.hljs:not(.shcb-wrap-lines) {
white-space: pre;
}

.wp-block-code code.hljs.shcb-wrap-lines {
white-space: pre-wrap;
}

.hljs.shcb-line-numbers {
border-spacing: 0;
counter-reset: line;
}

.hljs.shcb-line-numbers > .shcb-loc {
counter-increment: line;
}

.hljs.shcb-line-numbers .shcb-loc > span {
}

.hljs.shcb-line-numbers .shcb-loc::before {
border-right: 1px solid #ddd;
content: counter(line);
display: table-cell;
text-align: right;
-webkit-user-select: none;
-moz-user-select: none;
-ms-user-select: none;
user-select: none;
white-space: nowrap;
width: 1%;
}
.hljs > mark.shcb-loc { background-color: #ddf6ff; }String longestPalindrome(String str) {

if (str.length() <= 1)
return str;

String LPS = "";

for (int i = 1; i < str.length(); i++) {

// Consider odd length
int low = i;
int high = i;
// Keep extending in both left and right directions till the
// conditions for a palindrome are met
while(str.charAt(low) == str.charAt(high)) {
low--;
high++;

// Terminating condition if we reach the end/start of the string
if (low == -1 || high == str.length())
break;
}

// Indexes low and high can be used to extract the substring
String palindrome = str.substring(low+1, high);
if (palindrome.length() > LPS.length()) {
// Capture the longest palindrome found
LPS = palindrome;
}

// Consider even length
low = i - 1;
high = i;
while(str.charAt(low) == str.charAt(high)) {
low--;
high++;

if (low == -1 || high == str.length())
break;
}

palindrome = str.substring(low+1, high);
if (palindrome.length() > LPS.length()) {
// Similarly, keep a track of the longest even length palindrome
LPS = palindrome;
}
}

return LPS;
}
Code language: Java (java)

Time Complexity: O(n^2)
Space Complexity: O(n)

A working solution can be found here: https://ideone.com/GvH6g0
This code can also be obtained on Github.
A similar problem is available on Leetcode.
A similar question: length of longest palindrome that can be built from a string.

0 comment

#### You may also like

This site uses Akismet to reduce spam. Learn how your comment data is processed.

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More