# Unlock the complete Logicmojo experience for FREE

### 1 Million +

Strong Tech Community

### 500 +

Questions to Practice

Jobs Referrals

# Advanced Data Structures Algorithms & System Design(HLD+LLD) by Logicmojo

Cracking FAANG companies interviews with a few months of preparation

Learn Advanced Data Structures, Algorithms & System Design

Online live classes from 4 to 7 months programs

Get job assistance after course completion

# Longest Palindromic Substring

Back to home
Logicmojo - Updated Dec 12, 2023

## Problem Statement: Longest Palindromic Substring

Find and return the longest palindromic substring in a string str of length N. Substring of string str is str[i...j] where 0 <= i <= j < len(str)

Palindrome string:
A string which reads the same backwards that is if reverse(str) = str, then str is a palindrome. If there are more than one substring then return the substring that appears first.

Input Format : The string str is the first and only parameter.
Output Format : Return the longest palindromic substring of string str as a string.

For Example,
Input : mojologiccigolmojo
Output : logiccigol
Explanation : The longest palindromic substring is 10 characters long, and the string is logiccigol.

Input : abcdcbe
Outupt : bcdcb
Explanation : The longest palindromic substring is 5 characters long, and the string is bcdcb.

We have presented two approaches to find the longest palindromic substring :

• Brute Force Approach
• Dynamic Programming Approach
• Expand Around Center Approach

### Brute Force Approach

The most straightforward method is to check whether each substring is a palindrome or not. To begin, run three nested loops: the outer two loops pick all substrings one by one by fixing the corner characters, and the inner loop tests if the substring picked is palindrome or not.

It is important to note that every substring of length "1" is a palindrome in this context.

We'll therefore initially keep a variable that simply stores the length of our input string and another variable that simply stores the maximum length of the palindrome we have encountered so far. Reversing a string and comparing it to the original string, or substring in this case, is a useful approach to determine whether a string is a palindrome.

Time complexity : O(n^3).
Three nested loops are needed to find the longest palindromic substring in this approach, so the time complexity is O(n^3).
Space complexity : O(1).
As no extra space is needed.

C++ Implementation:

```#include <bits/stdc++.h>
using namespace std;

void longestPalindrome(string str)
{
int n = str.size();
int max = 1, start = 0;

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

for (int k = 0; k < (j - i + 1) / 2; k++)
if (str[i + k] != str[j - k])
flag = 0;

if (flag && (j - i + 1) > max) {
start = i;
max = j - i + 1;
}
}
}

for (int i = start; i <= start+max-1; ++i)
cout << str[i];
}

int main()
{
string str = "mojologiccigolmojo";
longestPalindrome(str);
return 0;
}

Try it Yourself

```

Java Implementation:

```class Main{

public static void longestPalindrome(String str)
{
int n = str.length();
int max = 1, start = 0;

for (int i = 0; i < str.length(); i++) {
for (int j = i; j < str.length(); j++) {
boolean flag = true;

for (int k = 0; k < (j - i + 1) / 2; k++)
if (str.charAt(i + k) != str.charAt(j - k))
flag = false;
if (flag && (j - i + 1) > max) {
start = i;
max = j - i + 1;
}
}
}

System.out.println(str.substring(start,start+max));

}

public static void main(String[] args)
{
String str = "mojologiccigolmojo";
longestPalindrome(str);

}
}

Try it Yourself

```

Python Implementation:

```def printSubStr(str, low, high):

for i in range(low, high + 1):
print(str[i], end = "")

def longestPalindrome(str):

n = len(str)

maxLength = 1
start = 0

for i in range(n):
for j in range(i, n):
flag = 1

for k in range(0, ((j - i) // 2) + 1):
if (str[i + k] != str[j - k]):
flag = 0

if (flag != 0 and (j - i + 1) > maxLength):
start = i
maxLength = j - i + 1

printSubStr(str, start, start + maxLength - 1)

if __name__ == '__main__':

str = "mojologiccigolmojo"

longestPalindrome(str)

Try it Yourself

```

### Dynamic Programming Approach

This problem can be resolved using dynamic programming, a more efficient variation of the prior method. To reiterate, dynamic programming works by splitting up larger problems into smaller ones and applying the output of computations on the smaller problems. The outcomes of the more manageable subproblems are retained and used.

Steps to solve the problem :

1. Keep a boolean table[n][n] that is filled from the bottom up.

2. If the substring is a palindrome, the value of table[i][j] is true; otherwise, it is false.

3. Check the value of table[i+1][j-1] before calculating table[i][j]. If the value is true and str[i] and str[j] are identical, then table[i][j] is true.

4. Otherwise, table[i][j] values is set to false.

5. We must fill out a table in advance for substrings of lengths=1 and lengths=2 since we are determining whether table[i+1][j-1] is true or false, therefore in the event of
If length == 1, let i=2, j=2 and (i+1,j-1) not lie between [i,j].
or, length == 2, let's say that i=2 and j=3, and that once more i+1 and j-1 do not lie between [i,j].

Time complexity : O(n^2).
Given that we need two nested traversals of the string, this strategy has a lower temporal complexity than the naïve or brute force solution, but it is still not the best option, so, the overall complexity is O(n^2).
Space complexity : O(n^2).
The dynamic programming approach's space complexity is O because we store the results of the subproblems in a table of size n * n. (n2).

C++ Implementation:

```#include <bits/stdc++.h>
using namespace std;

// Function to print a substring
void printSubs(
string s, int low, int high)
{
for (int i = low; i <= high; ++i)
cout << str[i];
}

// longest palindrome substring
int longestPalSubs(string s)
{
int n = s.size();

bool table[n][n];

memset(table, 0, sizeof(table));
int maxlen = 1;

for (int i = 0; i < n; ++i)
table[i][i] = true;

// check for sub-string of length 2.
int start = 0;
for (int i = 0; i < n - 1; ++i) {
if (s[i] == s[i + 1]) {
table[i][i + 1] = true;
start = i;
maxlen = 2;
}
}

// k is length of substring
for (int k = 3; k <= n; ++k) {
for (int i = 0; i < n - k + 1; ++i) {

// starting index i and length k
int j = i + k - 1;

if (table[i + 1][j - 1] && s[i] == s[j]) {
table[i][j] =  true;

if (k > maxlen) {
start = i;
maxlen = k;
}
}
}
}

cout << "Longest Palindrome Substring is: ";
printSubStr(s, start, start + maxLength - 1);

// return length of LongestPalindromeSubstring
return maxlen;
}

int main()
{
string s = "mojologiccigolmojo";
cout << "\nlen is: "
<< longestPalSubs(s);
return 0;
}

Try it Yourself

```

Java Implementation:

```public class longestPalSubstring {

// a substring s[low..high]
static void printSubs(
String s, int low, int high)
{
System.out.println(
s.subs(
low, high + 1));
}

// This function prints the longest
static int longestPalSubstr(String s)
{
// get length of input string
int n = s.len();

boolean table[][] = new boolean[n][n];

// All substrings of length 1 are palindromes
int maxlen = 1;
for (int i = 0; i < n; ++i)
table[i][i] = true;

// check for sub-string of length 2.
int start = 0;
for (int i = 0; i < n - 1; ++i) {
if (s.charAt(i) == s.charAt(i + 1)) {
table[i][i + 1] = true;
start = i;
maxlen = 2;
}
}

// k is length of substring
for (int k = 3; k <= n; ++k) {

for (int i = 0; i < n - k + 1; ++i) {

// starting index i and length k
int j = i + k - 1;

if (table[i + 1][j - 1]
&& s.charAt(i) == s.charAt(j)) {
table[i][j] = true;

if (k > maxlen) {
start = i;
maxlen = k;
}
}
}
}
System.out.print("Longest palindrome substring is; ");
printSubS(s, start,
start + maxlen - 1);

// return length of LongestPalindromeSubstring
return maxLength;
}
public static void main(String[] args)
{

String str = "mojologiccigolmojo";
System.out.println("len is: " + longestPalSubs(s));
}
}

Try it Yourself

```

Python Implementation:

```import sys

def printSubS(s, low, high) :
sys.stdout.write(st[low : high + 1])
sys.stdout.flush()
return ''

# This function prints the longest palindrome
def longestPalSubs(s) :
n = len(s)
table = [[0 for x in range(n)] for y
in range(n)]
maxlen = 1
i = 0
while (i < n) :
table[i][i] = True
i = i + 1

start = 0
i = 0
while i < n - 1 :
if (s[i] == s[i + 1]) :
table[i][i + 1] = True
start = i
maxlen = 2
i = i + 1

k = 3
while k <= n :
i = 0
while i < (n - k + 1) :

# index i and length k
j = i + k - 1

if (table[i + 1][j - 1] and
s[i] == s[j]) :
table[i][j] = True

if (k > maxlen) :
start = i
maxlen = k
i = i + 1
k = k + 1
print "Longest palindrome substring is: ", printSubS(s, start,
start + maxlen - 1)
# return length of LongestPalindromeSequence
return maxLength

s = "mojologiccigolmojo"
l = longestPalSubs(s)
print "Length is:", l

Try it Yourself

```

### Optimal Solution: Expand Around center

The concept is straightforward: take each character in the given string to be the midpoint of a palindrome and extend in both directions to discover the longest palindrome possible. For an even length palindrome, consider every adjacent pair of characters as the midpoint.

Let's take a example, for that palindrome is - "wowwow"

Time complexity : O(n^2).
Since expanding a palindrome around its center could take O(n) time, the overall complexity is O(n^2).
Space complexity : O(1).

C++ Implementation:

```#include <iostream>
#include <string>
using namespace std;

string expand(string str, int low, int high)
{
while (low >= 0 && high < str.length() && (str[low] == str[high])) {
low--, high++;
}
return str.substr(low + 1, high - low - 1);
}

string longestPalindromicSubstring(string str)
{
if (str.length() == 0) {
return str;
}

string max_str = "", curr_str;

int max_length = 0, curr_length;

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

curr_str = expand(str, i, i);
curr_length = curr_str.length();

if (curr_length > max_length)
{
max_length = curr_length;
max_str = curr_str;
}

curr_str = expand(str, i, i + 1);
curr_length = curr_str.length();

if (curr_length > max_length)
{
max_length = curr_length;
max_str = curr_str;
}
}

return max_str;
}

int main()
{
string str = "mojologiccigolmojo";

cout <<longestPalindromicSubstring(str);

return 0;
}

Try it Yourself

```

Java Implementation:

```#include <iostream>
#include <string>
using namespace std;

string expand(string str, int low, int high)
{
while (low >= 0 && high < str.length() && (str[low] == str[high])) {
low--, high++;
}
return str.substr(low + 1, high - low - 1);
}

string longestPalindromicSubstring(string str)
{
if (str.length() == 0) {
return str;
}

string max_str = "", curr_str;

int max_length = 0, curr_length;

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

curr_str = expand(str, i, i);
curr_length = curr_str.length();

if (curr_length > max_length)
{
max_length = curr_length;
max_str = curr_str;
}

curr_str = expand(str, i, i + 1);
curr_length = curr_str.length();

if (curr_length > max_length)
{
max_length = curr_length;
max_str = curr_str;
}
}

return max_str;
}

int main()
{
string str = "mojologiccigolmojo";

cout <<longestPalindromicSubstring(str);

return 0;
}

Try it Yourself

```

Python Implementation:

```def expand(s, low, high):
length = len(s)

while low >= 0 and high < length and s[low] == s[high]:
low = low - 1
high = high + 1

return s[low + 1:high]

def findLongestPalindromicSubstring(s):

if not s or not len(s):
return ''

max_str = ''

max_length = 0

for i in range(len(s)):
curr_str = expand(s, i, i)
curr_length = len(curr_str)

if curr_length > max_length:
max_length = curr_length
max_str = curr_str

curr_str = expand(s, i, i + 1)
curr_length = len(curr_str)

if curr_length > max_length:
max_length = curr_length
max_str = curr_str

return max_str

if __name__ == '__main__':

s = 'mojologiccigolmojo'

print(findLongestPalindromicSubstring(s))

Try it Yourself

```

With this article at Logicmojo, you must have the complete idea of solving Longes Palindromic Substring.