Longest Palindromic Substring LeetCode

Given a string s, return the longest palindromic substring in s.

 Example 1:

Input: s = "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Example 2:

Input: s = "cbbd"
Output: "bb"

Example 3:

Input: s = "a"
Output: "a"

Example 4:

Input: s = "ac"
Output: "a"

 NOTE:

• 1 <= s.length <= 1000
• s consist of only digits and English letters

This problem is very popular in LeetCode, GeeksForGeeks (here and here), and Wikipedia A collection of hundreds of interview questions and solutions are available in our blog at Interview Question Solutions
---------------------------------------------------------------------------
SOLUTION:

class LongestPalindromicSubstring {
    public static String longestPalindrome(String s) {
        if(s == null || s.length() == 0) {
            return "";
        }
       
        String longestPalindromicSubstring = "";
        for(int i = 0; i < s.length(); i++) {
            for(int j = i + 1; j <= s.length(); j++) {
//if this substring is longer than previous palindromesubstring and if this is a palindrome
                if(j - i > longestPalindromicSubstring.length() && isPalindrome(s.substring(i, j))) {
                    longestPalindromicSubstring = s.substring(i, j);
                }
            }
        }
       
        return longestPalindromicSubstring;
    }
   
    public static boolean isPalindrome(String s) {
        int i = 0;
        int j = s.length() - 1;
        while(i <= j) {
            if(s.charAt(i++) != s.charAt(j--)) {
                return false;
            }
        }
       
        return true;
    }

public static void main(String args[]){
String s= "babad";
s = "bbbab";
System.out.println("String :"+s+" has longest palindrome as:"+longestPalindrome(s));
}
}

Source code: Java (solution 1, solution 2)

	/*
	Given a string, find the longest substring which is palindrome.
	For example, if the given string is “forgeeksskeegfor”, the output should be “geeksskeeg”.
	*/
	package com.alg.dp;
	import java.util.ArrayList;
	import java.util.List;
	/**
	*
	* @author rbaral
	*/
	public class LongestPalindromesubstring {
	/**
	* reverse the string and compare entries in the original and the reversed string
	* @param s
	* @return
	*/
	public static String longestPalSubstr(String s){
	char[] rev = new char[s.length()];
	for(int i=s.length()-1; i>=0; i--)
	rev[s.length() - i -1] = s.charAt(i);
	StringBuffer pal = new StringBuffer();
	List<String> palsList = new ArrayList<String>();
	for(int i=0; i< s.length(); i++){
	if(s.charAt(i)==rev[i]){
	pal.append(s.charAt(i));
	}else{
	//that was the last palindrome we found so far, save it in cache and check for another
	palsList.add(pal.toString());
	pal.delete(0, pal.length());
	}
	}
	//now check which one is the longest palindrome found so far and return that
	String longestPal = "";
	for(String ss: palsList){
	System.out.println("potential pal is:"+ss);
	if(ss.length()> longestPal.length()){
	longestPal = ss;
	}
	}
	return longestPal;
	}
	public static void main(String[] args) {
	String str = "forgeeksskeegfor";
	//str = "abcd";
	System.out.println("Length is: " +
	longestPalSubstr(str));
	}
	}

view raw LongestPalindromicSubstring.java hosted with ❤ by GitHub

	/**
	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 LongestPalindromicSubstring{
	/**
	dp(i, j) represents whether s(i ... j) can form a palindromic substring, dp(i, j) is true when s(i) equals to s(j) and s(i+1 ... j-1) is a palindromic substring. When we found a palindrome, check if it's the longest one. Time complexity O(n^2).
	*/
	public static String longestPalindrome(String s) {
	int n = s.length();
	String res = "";
	boolean[][] dp = new boolean[n][n];
	for (int i = n - 1; i >= 0; i--) {
	for (int j = i; j < n; j++) {
	System.out.println(i+"..."+j+"...n is:"+n);
	dp[i][j] = s.charAt(i) == s.charAt(j) && (j - i < 3 || dp[i + 1][j - 1]);
	if (dp[i][j] && (j - i + 1 > res.length())) {
	res = s.substring(i, j + 1);
	}
	}
	}
	return res;
	}
	public static void main(String args[]){
	String s= "babad";
	s = "bbbab";
	System.out.println("String :"+s+" has longest palindrome as:"+longestPalindrome(s));
	}
	}

view raw LongestPalindromicSubstringII.java hosted with ❤ by GitHub