# Longest Palindrome Substring - Leet Code Solution

August 27, 2019

## Problem Statement

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

``````Example 1:

Output: "bab"
Note: "aba" is also a valid answer.

Example 2:

Input: "cbbd"
Output: "bb"``````

## Brute Force Solution

• Find all substrings of a string
• Check if that substring is a palindrome string
• Keep a track of longest palindrome string found so far

Simple!

### Code

``````public class Q5_LongestPalindromeSubstring_Simple {
private String str;

public Q5_LongestPalindromeSubstring_Simple(String str) {
this.str = str;
}

private boolean isPalindrome(String s) {
int lastIndex = s.length()-1;
int startIndex = 0;
while (startIndex < s.length() && lastIndex >= 0) {
if (s.charAt(startIndex) != s.charAt(lastIndex)) {
return false;
}
startIndex ++;
lastIndex --;
}
return true;
}

public String longestPalindrome() {
String max = "";

//generate all substrings
for (int i=0; i<this.str.length(); i++) {
for (int j=i+1; j<this.str.length(); j++) {
String substring = this.str.substring(i, j);
if (this.isPalindrome(substring)) {
if (max.length() < substring.length()) {
max = substring;
}
}
}
}

return max;
}
}``````

### Runtime Complexity

It is O(n^3)

• O(n^2) in find all substrings
• For every substring, find out if it is a palindrome - O(n)

## Optimized Solution

For optimized solutions, we should go deeper into the requirements. What is palindrome. It can be found in two ways:

• Centered around a single character. Length will be odd. Example: abc
• Centered around two characters. Length will be even. Example: abba

The solution is around starting from the one element, and try to expand it from both sides. Expand it till you find same character.

### Algorithm

• Iterate over string
• Try to expand it in two ways. Around single character and around two characters
• Keep track of max found palindrome substring

### Code

``````public class Q5_LongestPalindromeSubstring_Optimized {
private String str;

public Q5_LongestPalindromeSubstring_Optimized(String str) {
this.str = str;
}

//expanding around elements passed
private String findPalindrome(int startIndex, int endIndex) {
String palindrome = "";
while (startIndex >= 0 && endIndex < this.str.length() && this.str.charAt(startIndex) == this.str.charAt(endIndex)) {
palindrome = this.str.substring(startIndex, endIndex+1);
startIndex --;
endIndex ++;
}

return palindrome;
}

public String longestPalindrome() {
String max = "";

for (int i=0; i<this.str.length()-1; i++) {
String s1 = this.findPalindrome(i, i);
String s2 = this.findPalindrome(i,  i+1);

String maxOfTwo = s1.length() > s2.length() ? s1 : s2;
if (max.length() < maxOfTwo.length()) {
max = maxOfTwo;
}
}

return max;
}
}
``````

## Similar Posts

### Find the Median of Two Sorted Arrays - Leet Code Solution

Problem Statement There are two sorted arrays nums1 and nums2 of size m and n…

### Coding Interview - Useful Terms Cheatsheet

Big-O notation In simpler terms, its kind of a unit to measure how efficient an…

### Valid Palindrome - Leet Code Solution

Problem Statement Given a string, determine if it is a palindrome, considering…

In this post, we will see some of the frequently used concepts/vocabulary in…

### Three Sum Closest - Leet Code Solution

Problem Statement Given an array nums of n integers and an integer target, find…

### Check whether number is palindrome or not - Leet Code Solution

Problem Statement Determine whether an integer is a palindrome. An integer is a…

## Latest Posts

### Python SMTP Email Code - How to Send HTML Email from Python Code with Authentication at SMTP Server

Introduction This post has the complete code to send email through smtp server…

### Python SMTP Email Code - Sender Address Rejected - Not Owned By User

Introduction In a normal email sending code from python, I’m getting following…

### Nodejs with MongoDB - Number of Opened Connections Keep on Increasing with Mongoose Library

Introduction In one of my app, I was using to talk to . I have used some event…

### Django Python - How to Build Docker Image and Run Web-service on Apache with Python 3.9

Introduction So you have a Django project, and want to run it using docker image…

### Python - How to Maintain Quality Build Process Using Pylint and Unittest Coverage With Minimum Threshold Values

Introduction It is very important to introduce few process so that your code and…

### Example Jenkin Groovy Pipeline Script for Building Python Projects with Git Events and Push to Artifactory

Introduction In this post, we will see a sample Jenkin Pipeline Groovy script…