# Solution For Longest Palindrome

The problem is to find the longest palindrome substring in a given string.

Solution:

One way to solve this problem is to use a dynamic programming approach. We can create a 2D boolean array dp[l][r], where dp[l][r] is true if the substring from index l to index r in the string s is a palindrome. The base cases are when l=r and l=r+1.

The recurrence relation is:

• dp[l][r] = true if dp[l+1][r-1] is true and s[l] = s[r]
• dp[l][r] = false if s[l] != s[r]

We can initialize the dp array with all false values and then fill it in from the bottom up and left to right.

Algorithm:

1. Initialize a 2D boolean array dp with size n*n where n is the length of the input string s.
2. Initialize all diagonal elements dp[i][i] and dp[i][i+1] (i.e., substrings of length 1 and 2) as true.
3. Traverse the input string s starting from length 3 and iterate over all possible substrings of length i from j, where dp[j][j+i-1] is true if s[j] = s[j+i-1] and dp[j+1][j+i-2] is true.
4. Update longest_palindrome if the length of the current substring (i.e., j+i-1-j+1) is greater than the current longest_palindrome.
5. Return longest_palindrome.

Time Complexity: O(n^2)

Let’s implement the above algorithm:

Python Code:

class Solution:
def longestPalindrome(self, s: str) -> str:
n = len(s)
dp = [[False for j in range(n)] for i in range(n)]

``````    longest_palindrome = ""
for i in range(n):
dp[i][i] = True
longest_palindrome = s[i]

for i in range(n-1):
if s[i] == s[i+1]:
dp[i][i+1] = True
longest_palindrome = s[i:i+2]

for i in range(3, n+1):
for j in range(n-i+1):
k = j + i - 1
if s[j] == s[k] and dp[j+1][k-1]:
dp[j][k] = True
if i > len(longest_palindrome):
longest_palindrome = s[j:k+1]

return longest_palindrome
``````

Input:

Output:

“bab”

Explanation:

The longest palindromic substring in “babad” is “bab”.

## Step by Step Implementation For Longest Palindrome

```public class Solution {
public int longestPalindrome(String s) {
if (s == null || s.length() == 0) return 0;
HashSet set = new HashSet();
int count = 0;
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (set.contains(c)) {
set.remove(c);
count++;
} else {
}
}
if (!set.isEmpty()) return count * 2 + 1;
return count * 2;
}
}```
```class Solution:
def longestPalindrome(self, s: str) -> str:
# Base cases
if len(s) == 0:
return ""
if len(s) == 1:
return s

# Initialize max_length and max_substring
max_length = 1
max_substring = s[0]

# Iterate through the string
for i in range(len(s)):

# For odd length palindromes
curr_length = self.find_palindrome_length(s, i, i)
if curr_length > max_length:
max_length = curr_length
max_substring = s[i-max_length+1:i+1]

# For even length palindromes
curr_length = self.find_palindrome_length(s, i, i+1)
if curr_length > max_length:
max_length = curr_length
max_substring = s[i-max_length+1:i+2]

return max_substring

# Helper function to find the length of a palindrome centered at i, j
def find_palindrome_length(self, s, i, j):
while i >= 0 and j < len(s) and s[i] == s[j]:
i -= 1
j += 1
return j-i-1```
```var longestPalindrome = function(s) {
let longest = "";

for (let i = 0; i < s.length; i++) {
for (let j = i + 1; j <= s.length; j++) {
const current = s.slice(i, j);
if (isPalindrome(current) && current.length > longest.length) {
longest = current;
}
}
}

return longest;
};

function isPalindrome(s) {
let left = 0;
let right = s.length - 1;

while (left < right) {
if (s[left] !== s[right]) {
return false;
}

left++;
right--;
}

return true;
}```
```class Solution {
public:
int longestPalindrome(string s) {
// Corner cases
if (s.length() == 0) return 0;
if (s.length() == 1) return 1;

// Initialize variables
int n = s.length();
int max_len = 1;
bool table[n][n];
memset(table, 0, sizeof(table));

// Fill the table for substrings of length 2
for (int i = 0; i < n-1; i++) {
if (s[i] == s[i+1]) {
table[i][i+1] = true;
max_len = 2;
}
}

// Fill the table for substrings of length 3 and above
for (int k = 3; k <= n; k++) {
for (int i = 0; i < n-k+1; i++) {
int j = i+k-1;
if (table[i+1][j-1] && s[i] == s[j]) {
table[i][j] = true;
if (k > max_len) max_len = k;
}
}
}

return max_len;
}
};```
```public class Solution {
public int LongestPalindrome(string s) {
if (string.IsNullOrEmpty(s))
{
return 0;
}
int maxLength = 1;
int start = 0;
int low, high;

// One by one consider every character as center point of
// even and length palindromes
for (int i = 1; i < s.Length; ++i)
{
// Find the longest even length palindrome with center
// points as i-1 and i.
low = i - 1;
high = i;
while (low >= 0 && high < s.Length && s[low] == s[high])
{
if (high - low + 1 > maxLength)
{
start = low;
maxLength = high - low + 1;
}
--low;
++high;
}

// Find the longest odd length palindrome with center
// point as i
low = i - 1;
high = i + 1;
while (low >= 0 && high < s.Length && s[low] == s[high])
{
if (high - low + 1 > maxLength)
{
start = low;
maxLength = high - low + 1;
}
--low;
++high;
}
}

return maxLength;
}
}```
Scroll to Top

## Top 100 Leetcode Practice Problems In Java

Get 30% Off Instantly!
[gravityforms id="5" description="false" titla="false" ajax="true"]