Valid Palindrome - Leet Code Solution
Problem Statement Given a string, determine if it is a palindrome, considering…
August 27, 2019
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
Example 1:
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.
Example 2:
Input: "cbbd"
Output: "bb"
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;
}
}
It is O(n^3)
For optimized solutions, we should go deeper into the requirements. What is palindrome. It can be found in two ways:
The solution is around starting from the one element, and try to expand it from both sides. Expand it till you find same character.
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;
}
}
Problem Statement Given a string, determine if it is a palindrome, considering…
Problem The Leetcode file system keeps a log each time some user performs a…
Problem Statement Maximum Length of Subarray With Positive Product. Given an…
System design interview is pretty common these days, specially if you are having…
First try to understand question. Its a binary tree, not a binary search tree…
Min Priority Queue is a data structure which manage a list of keys(values). And…
In this post, we will see some of the frequently used concepts/vocabulary in…
System design interview is pretty common these days, specially if you are having…
Introduction You are given an array of integers with size N, and a number K…
Graph Topological Sorting This is a well known problem in graph world…
Problem Statement Given a Binary tree, print out nodes in level order traversal…
Problem Statement Given an array nums of n integers and an integer target, are…