`Manacher's algorithm`

is used to find the longest palindromic substring in any string. It is required to solve sub-problems of some very hard problems. The problem statement it solves is: *Given a string 's' with the length of 'n'. Find the longest palindromic substring in the given string. A string is a palindrome when it is equal to the reverse of itself.*

`Manacher's algorithm`

was invented by Manacher for listing all the palindromes that appear at the start of any given string, it was later observed that the same algorithm can be used to find the longest palindromic substring of any string in linear time.

## Scope of the Article

- In this article, we will learn how to find the
`longest palindromic substring`

in any given string. - We will discuss how to do it using the brute force approach and
`Manacher's algorithm`

. - Every step in the algorithm will be explained thoroughly.
- Implementations will be explained using comments at each step.
- We will understand the Complexity Analysis of each implementation.

## Takeaways

- Complexity of
`Manacher's algorithm`

`Time complexity`

– $O(N)$.

## Brute Force Approach

The brute force / naive approach is slower than `Manacher's algorithm`

, but it is a good stepping stone for understanding the problem and `Manacher's algorithm`

. The Brute force approach is to check each substring of the given string whether the substring is a palindrome or not.

To implement the brute force approach, first, we will use a nested loop to get each substring, and then nest another loop to check whether that substring is a palindrome or not.

**Implementation in C++ 17**

```
// C++ solution for Longest Palindromic Substring (Brute Force)
#include <iostream>
using namespace std;
// A function to print a substring.
void printSubstring(string str, int left, int right){
for (int i = left; i <= right; i++)
cout << str[i];
}
// A function to get the longest palindromic substring
// in the a given string using Brute Force Approach.
void longestPalSubstring(string str){
// Getting length of the input string
int n = str.size();
// All substrings of length 1 are palindromes
int maxLength = 1;
int start = 0;
// Checking all the substrings
for (int i = 0; i < n; i++){
for (int j = i; j < n; j++){
int flag = 1;
// Checking for a palindromic subtring
for (int k = 0; k < (j - i + 1) / 2; k++)
if (str[i + k] != str[j - k])
flag = 0;
// If substring is palindromic
if (flag && (j - i + 1) > maxLength){
start = i;
maxLength = j - i + 1;
}
}
}
// Printing the longest Palindromic substring
cout << "The Longest Palindromic Substring is: ";
printSubstring(str, start, start + maxLength - 1);
}
// Driver Code
int main(){
string str = "daabddfddbegtd";
longestPalSubstring(str);
return 0;
}
```

**Implementation in Python 3**

```
# Python solution for Longest Palindromic Substring (Brute Force)
# A function to print a substring.
def printSubstring(str, left, right):
for i in range(left, right + 1):
print(str[i], end="")
# A function to get the longest palindromic substring in a
# given string using Brute Force Approach.
def longestPalSubstring(str):
# Getting length of the input string
n = len(str)
# All substrings of length 1 are palindromes
maxLength = 1
start = 0
# Checking all the substrings
for i in range(n):
for j in range(i, n):
flag = 1
# Checking for a palindromic subtring
for k in range(0, ((j - i) // 2) + 1):
if str[i + k] != str[j - k]:
flag = 0
# If substring is palindromic
if flag != 0 and (j - i + 1) > maxLength:
start = i
maxLength = j - i + 1
# Printing the longest Palindromic substring
print("The Longest Palindromic Substring is: ", end="")
printSubstring(str, start, start + maxLength - 1)
# Driver Code
if __name__ == '__main__':
my_string = "daabddfddbegtd"
longestPalSubstring(my_string)
```

**Implementation in Java 8**

```
// Java solution for Longest Palindromic Substring (Brute Force)
import java.util.*;
class Manacher{
// A function to print a substring.
static void printSubstring(String str, int left, int right){
for (int i = left; i <= right; i++)
System.out.print(str.charAt(i));
}
// # A function to get the longest palindromic
// substring in the a given string using Brute Force Approach
static void longestPalSubstring(String str){
// Getting length of the input string
int n = str.length();
// All substrings of length 1 are palindromes
int maxLength = 1, start = 0;
// Checking all the substrings
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
int flag = 1;
// Checking for a palindromic subtring
for (int k = 0; k < (j - i + 1) / 2; k++)
if (str.charAt(i + k) != str.charAt(j - k))
flag = 0;
// If substring is palindromic
if (flag!=0 && (j - i + 1) > maxLength) {
start = i;
maxLength = j - i + 1;
}
}
}
// Printing the longest Palindromic substring
System.out.print("The Longest Palindromic Substring is: ");
printSubstring(str, start, start + maxLength - 1);
}
// Driver Code
public static void main(String[] args) {
String str = "daabddfddbegtd";
longestPalSubstring(str);
}
}
```

The output is the same for all of these (the implementation is the same, the difference is only of the programming languages).

**Output**

`The Longest Palindromic Substring is: bddfddb`

In the above examples, we are using the brute force approach to find the `longest palindromic substring`

in the given string.

The printSubstring() function is used for printing a substring, longestPalSubstring() is used to print the `longest palindromic substring`

.

### Time Complexity:

$O(N^{3})$

In the brute force approach, three nested loops are used to find the `longest palindromic substring`

, so the time complexity will be $O(N^{3})$.

### Space Complexity

$O(1)$

No extra space is needed in this approach, so the space complexity will be $O(1)$.

## Manacher’s algorithm

`Manacher's algorithm`

is used to find the longest palindromic substring in any given string. This algorithm is faster than the brute force approach, as it exploits the idea of a palindrome happening inside another palindrome.

`Manacher's algorithm`

is designed to find the palindromic substrings with odd lengths only. To use it for even lengths also, we tweak the input string by inserting the character “`#`

” at the beginning and each alternate position after that (changing “`abcaac`

” to “`#a#b#c#a#a#c#`

“).

In the case of an odd length palindrome, the middle character will be a character of the original string, surrounded by “`#`

“.

In the case of an even length palindrome, the middle character will be a “#” character.

Now we will learn each of its steps for a deeper understanding, which will help us in its implementation.

## Steps of the Manacher’s Algorithm

Steps of the Manacher’s algorithm are as follows:

- Create an array or a list ($sChars$) of length $strLen$ which is $2 * n + 3$ ($n$ being the length of the given string), to modify the given string.
- Assign the first and last element of $sChars$ to be “
`@`

” and “`$`

“, respectively. - Fill the blank spaces in $sChars$ by characters of the given string and “#” alternatively.
- Declare variables

- Implicating maximum detected length of palindrome substring $maxLen = 0$
- Position from where to start searching $start = 0$
- Highest position of the extreme right character of all detected palindromes $maxRight = 0$
- Center of the detected palindrome $center = 0$.

- Create an array or a list $p$ to record the width of each palindrome about their center, center being the corresponding characters in $sChars$.
- Create a for loop iterating from $1$ to $strLen – 1$, with $i$ incrementing in each iteration.
- In each iteration, check if $i < maxRight$, if yes, then assign minimum of $maxRight – i$ and $p[2 * center – i]$ to $p[i]$.
- Nest a while loop inside the for loop, to count with width along the center, condition being, $sChars[i + p[i] + 1]$ is equal to $sChars[i – p[i] – 1]$, if yes, increment $p[i]$ by 1.
- To update center, check if $i + p[i]$ is greater than $maxRight$, if yes, assign $center$ to be $1$, and $maxRight$ to be $i + p[i]$.
- For updating the Maximum length detected, check if $p[i]$ is greater than $maxLen$, if yes, then assign $start$ to be $(i – p[i] – 1) / 2$, and $maxLen$ to be $p[i]$.
- Come out of the for loop, and print the substring in the given string, starting from $start$ and ending at $start + maxLen – 1$.

## Implementation of Manacher’s Algorithm

Now we will implement `Manacher's algorithm`

in C++17, Java 8, and Python 3

**Things to Note:**

- $strLen$ is the length of the modified (after inserting extra characters) list/array.
- $sChars$ is the modified (after inserting extra characters) list/array.
- $maxLen$ is the length of the longest palindrome detected.
- $start$ is the position from which we have to search for a palindrome.
- $maxRight$ is the position of the rightmost character of a palindrome.
- $center$ is the center of a palindrome
- $p$ is the list/array of the width of palindromes about their center, center being the corresponding characters in $sChars$.

**Implementation in C++ 17**

```
// C++ solution for Longest Palindromic Substring (Manacher's Algorithm)
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// A function to print a substring.
void printSubstring(string str, int left, int right){
for (int i = left; i <= right; i++)
cout << str[i];
}
// Implementation of Manacher's Algorithm
void longestPalSubstring(string s){
/*
If length of given string is n then its length after
inserting n+1 "#", one "@", and one "$" will be
(n) + (n+1) + (1) + (1) = 2n+3
*/
int strLen = 2 * s.length() + 3;
char* sChars = new char[strLen];
/*
Inserting special characters to ignore special cases
at the beginning and end of the array
"abc" -> @ # a # b # c # $
"" -> @#$
"a" -> @ # a # $
*/
sChars[0] = '@';
sChars[strLen - 1] = '$';
int t = 1;
for (char c : s){
sChars[t++] = '#';
sChars[t++] = c;
}
sChars[t] = '#';
int maxLen = 0;
int start = 0;
int maxRight = 0;
int center = 0;
int* p = new int[strLen]; // i's radius, which doesn't include i
for(int i = 1; i < strLen - 1; i++){
if (i < maxRight){
p[i] = min(maxRight - i, p[2 * center - i]);
}
// Expanding along the center
while (sChars[i + p[i] + 1] == sChars[i - p[i] - 1]){
p[i]++;
}
// Updating center and its bound
if (i + p[i] > maxRight){
center = i;
maxRight = i + p[i];
}
// Updating ans
if (p[i] > maxLen){
start = (i - p[i] - 1) / 2;
maxLen = p[i];
}
}
// Printing the longest palindromic substring
cout << "The Longest Palindromic Substring is: ";
printSubstring(s, start, start + maxLen - 1);
}
// Driver Code
int main(){
string str = "daabddfddbegtd";
longestPalSubstring(str);
return 0;
}
```

**Implementation in Python 3**

```
# Python solution for Longest Palindromic Substring (Manacher's Algorithm)
# A function to print a substring.
def printSubstring(str, left, right):
for i in range(left, right + 1):
print(str[i], end="")
# Implementation of Manacher's Algorithm
def longestPalSubstring(s):
# If length of given string is n then its length after
# inserting n+1 "#", one "@", and one "$" will be
# (n) + (n+1) + (1) + (1) = 2n+3
strLen = 2 * len(s) + 3
sChars = [0]*strLen
# Inserting special characters to ignore special cases
# at the beginning and end of the array
# "abc" -> @ # a # b # c # $
# "" -> @#$
# "a" -> @ # a # $
sChars[0] = '@'
sChars[strLen - 1] = '$'
t = 1
for i in s:
sChars[t] = '#'
t += 1
sChars[t] = i
t += 1
sChars[t] = '#'
maxLen = int(0)
start = int(0)
maxRight = int(0)
center = int(0)
p = [0] * strLen # i's radius, which doesn't include i
for i in range(1, strLen - 1):
if i < maxRight:
p[i] = min(maxRight - i, p[2 * center - i])
# Expanding along the center
while sChars[i + p[i] + 1] == sChars[i - p[i] - 1]:
p[i] += 1
# Updating center and its bound
if i + p[i] > maxRight:
center = i
maxRight = i + p[i]
# Updating ans
if p[i] > maxLen:
start = int((i - p[i] - 1) / 2)
maxLen = p[i]
# Printing the longest Palindromic substring
print("The Longest Palindromic Substring is: ", end="")
printSubstring(s, start, start + maxLen - 1)
return
# Driver Code
if __name__ == '__main__':
my_string = "daabddfddbegtd"
longestPalSubstring(my_string)
```

**Implementation in Java 8**

```
// Java solution for Longest Palindromic Substring (Manacher's Algorithm)
class Manacher {
// A function to print a substring.
static void printSubstring(String str, int left, int right){
for (int i = left; i <= right; i++)
System.out.print(str.charAt(i));
}
// Implementation of Manacher's Algorithm
public static void longestPalSubstring(String s) {
/*
If length of given string is n then its length after
inserting n+1 "#", one "@", and one "$" will be
(n) + (n+1) + (1) + (1) = 2n+3
*/
int strLen = 2 * s.length() + 3;
char[] sChars = new char[strLen];
/*
Inserting special characters to ignore special cases
at the beginning and end of the array
"abc" -> @ # a # b # c # $
"" -> @#$
"a" -> @ # a # $
*/
sChars[0] = '@';
sChars[strLen - 1] = '$';
int t = 1;
for (char c : s.toCharArray()) {
sChars[t++] = '#';
sChars[t++] = c;
}
sChars[t] = '#';
int maxLen = 0;
int start = 0;
int maxRight = 0;
int center = 0;
int[] p = new int[strLen]; // i's radius, which doesn't include i
for (int i = 1; i < strLen - 1; i++) {
if (i < maxRight) {
p[i] = Math.min(maxRight - i, p[2 * center - i]);
}
// Expanding along the center
while (sChars[i + p[i] + 1] == sChars[i - p[i] - 1]) {
p[i]++;
}
// Updating center and its bound
if (i + p[i] > maxRight) {
center = i;
maxRight = i + p[i];
}
// Updating ans
if (p[i] > maxLen) {
start = (i - p[i] - 1) / 2;
maxLen = p[i];
}
}
// Printing the longest Palindromic substring
System.out.print("The Longest Palindromic Substring is: ");
printSubstring(s, start, start + maxLen - 1);
}
// Driver Code
public static void main(String[] args){
String str = "daabddfddbegtd";
longestPalSubstring(str);
}
}
```

The output is the same for all of these (the implementation is the same, the difference is only of the programming languages).

**Output**

`The Longest Palindromic Substring is: bddfddb`

In the above examples, we are using the `Manacher’s algorithm`

to find the longest palindromic substring in the given string.

The `printSubstring()`

function is used for printing a substring, `longestPalSubstring()`

is used to print the longest palindromic substring.

## Complexity Analysis of Manacher’s Algorithm

Analysing the Time and Spatial complexity of `Manacher's algorithm`

($N$ here is the number of characters inside the given string):

### Time Complexity:

$O(N)$

At the first glance, it may seem that the algorithm has a $O(N^2)$ time complexity due to nested loops, but that’s not the case, a more careful analysis shows that the algorithm is linear and amortized.

Each successful comparison results in $maxRight$ moving one step forward, and it never reduces, therefore, the inner while loop gets executed at most $n$ times. Hence, the time complexity of `Manacher's algorithm`

will be $O(N).$

### Space Complexity:

$O(N)$

We need $O(n)$ space to create and form $p$ (palindrome width).

*Boost Your Tech Profile! Join Our DSA Courses for Advanced Algorithmic Mastery. Enroll Now to Stand Out in the Coding Landscape!*

## Conclusion

`Manacher's Algorithm`

is used to find the longest palindrome substring in a given string.- Finding the longest palindrome using the Brute Force algorithm is very slow, time complexity being $O(N^3)$.
- The given string needs to be modified by inserting a special character at every alternate position to work it with
`Manacher's algorithm`

in every case. - Time Complexity of
`Manacher's algorithm`

is $O(N)$. - Space Complexity of
`Manacher's algorithm`

is $O(N)$.