# 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

### Remove nth Node from Last - Leet Code Solution

Problem Statement Given a linked list, remove the n-th node from the end of list…

### Graph Topological Sorting - Build System Order Example

Graph Topological Sorting This is a well known problem in graph world…

### Valid Palindrome - Leet Code Solution

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

### Determine if a string has all unique characters

Problem Implement an algorithm to determine if a string has all the characters…

### Selection Sort Algorithm

It is one of a simple algorithm to study for a beginner to understanding sorting…

### Two Sum Problem - Leet Code Solution

Problem Statement Given an array of integers, return indices of the two numbers…

## Latest Posts

### Jenkins Pipeline with Jenkinsfile - How To Schedule Job on Cron and Not on Code Commit

Introduction In this post we will see following: How to schedule a job on cron…

### How to Git Clone Another Repository from Jenkin Pipeline in Jenkinsfile

Introduction There are some cases, where I need another git repository while…

### How to Fetch Multiple Credentials and Expose them in Environment using Jenkinsfile pipeline

Introduction In this post, we will see how to fetch multiple credentials and…

### Jenkins Pipeline - How to run Automation on Different Environment (Dev/Stage/Prod), with Credentials

Introduction I have an automation script, that I want to run on different…

### Jenkinsfile - How to Create UI Form Text fields, Drop-down and Run for Different Conditions

Introduction I had to write a CICD system for one of our project. I had to…

### Java Log4j Logger - Programmatically Initialize JSON logger with customized keys in json logs

Introduction Java log4j has many ways to initialize and append the desired…