Remove nth Node from Last - Leet Code Solution
Problem Statement Given a linked list, remove the n-th node from the end of list…
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"
Simple!
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 linked list, remove the n-th node from the end of list…
Graph Topological Sorting This is a well known problem in graph world…
Problem Statement Given a string, determine if it is a palindrome, considering…
Problem Implement an algorithm to determine if a string has all the characters…
It is one of a simple algorithm to study for a beginner to understanding sorting…
Problem Statement Given an array of integers, return indices of the two numbers…
Introduction In this post we will see following: How to schedule a job on cron…
Introduction There are some cases, where I need another git repository while…
Introduction In this post, we will see how to fetch multiple credentials and…
Introduction I have an automation script, that I want to run on different…
Introduction I had to write a CICD system for one of our project. I had to…
Introduction Java log4j has many ways to initialize and append the desired…