A Collection of Code Snippets in as Many Programming Languages as Possible

This project is maintained by TheRenegadeCoder

Welcome to the Longest Palindromic Substring page! Here, you'll find a description of the project as well as a list of sample programs written in various languages.

This article was written by:

- Jeremy Grifski
- Ron Zuckerman

Palindrome is a phenomenon, where a string has same sequence of letters when read start –> end and end –> start.

Let's say we have a string,

```
s = 'paapaapap'
```

Here, we have seven palindromic substrings.

```
sub_1 = 'aa'
sub_2 = 'paap'
sub_3 = 'paapaap'
sub_4 = 'aapaa'
sub_5 = 'apap'
sub_6 = 'pap'
sub_7 = 'apaapa'
```

Out of the seven, `sub_3 = 'paapaap'`

is the longest. hence the output would be `'paapaap'`

This problem can be solved using 3 methods.

The simple approach is to check each substring whether the substring is a palindrome or not. We can run three loops, the outer two loops pick all substrings one by one by fixing the corner characters, the inner loop checks whether the picked substring is palindrome or not.

- Time complexity: O(n
^{3}) - Auxiliary complexity: O(1)

The time complexity can be reduced by storing results of subproblems. We maintain a boolean table[n][n] that is filled in bottom up manner. The value of table[i][j] is true, if the substring is palindrome, otherwise false. To calculate table[i][j], we first check the value of table[i+1][j-1], if the value is true and str[i] is same as str[j], then we make table[i][j] true. Otherwise, the value of table[i][j] is made false.

- Time complexity: O(n
^{2}) - Auxiliary Space: O(n
^{2})

The time complexity of the Dynamic Programming based solution is O(n^{2}) and it requires O(n^{2}) extra space. We can find the longest palindrome substring in O(n^{2}) time with O(1) extra space. The idea is to generate all even length and odd length palindromes and keep track of the longest palindrome seen so far.

Fix a center and expand in both directions for longer palindromes.

Fix two center (low and high) and expand in both directions for longer palindromes.

- Time complexity: O(n
^{2}) where n is the length of input string. - Auxiliary Space: O(1)

Every project in the Sample Programs repo should be tested. In this section, we specify the set of tests specific to Longest Palindromic Substring. In order to keep things simple, we split up the testing as follows:

- Lps Valid Tests
- Lps Invalid Tests

Description | Input | Output |
---|---|---|

Sample Input: One Palindrome | "racecar" | "racecar" |

Sample Input: Two Palindrome | "kayak mom" | "kayak" |

Sample Input: Complex Palindrome | "step on no pets" | "step on no pets" |

Description | Input |
---|---|

No Input | |

Empty Input | "" |

Invalid Input: No Palindromes | "polip" |

All of these tests should output the following:

```
Usage: please provide a string that contains at least one palindrome
```

- Longest Palindromic Substring in Algol68
- Longest Palindromic Substring in Beef
- Longest Palindromic Substring in Commodore Basic
- Longest Palindromic Substring in Euphoria
- Longest Palindromic Substring in Go
- Longest Palindromic Substring in Javascript
- Longest Palindromic Substring in Mathematica
- Longest Palindromic Substring in Php
- Longest Palindromic Substring in Python
- Longest Palindromic Substring in Rust