Return String instead of length

[krish]

Hi,

Can you please help how to return the Longest Palindromic String itself?

Thanks,
Krishna.

[Design_Gurus]

Sure, here is the code to return the longest palindrome instead. We need to track the start and the end indexes of the palindrome and keep updating them whenever we find a bigger palindrome. Core change is as follows:

            if (maxLength < endIndex - startIndex + 1) {
              palindromeStart = startIndex;
              palindromeEnd = endIndex;
              maxLength = endIndex - startIndex + 1;
            }

Here is the full code:

class LPS {

  public String findLPSLength(String st) {
    // dp[i][j] will be 'true' if the string from index 'i' to index 'j' is a
    // palindrome
    boolean[][] dp = new boolean[st.length()][st.length()];

    // every string with one character is a palindrome
    for (int i = 0; i < st.length(); i++)
      dp[i][i] = true;

    int maxLength = 1;
    int palindromeStart = 0, palindromeEnd = 0;
    for (int startIndex = st.length() - 1; startIndex >= 0; startIndex--) {
      for (int endIndex = startIndex + 1; endIndex < st.length(); endIndex++) {
        if (st.charAt(startIndex) == st.charAt(endIndex)) {
          // if it's a two character string or if the remaining string is a palindrome too
          if (endIndex - startIndex == 1 || dp[startIndex + 1][endIndex - 1]) {
            dp[startIndex][endIndex] = true;
            if (maxLength < endIndex - startIndex + 1) {
              palindromeStart = startIndex;
              palindromeEnd = endIndex;
              maxLength = endIndex - startIndex + 1;
            }
          }
        }
      }
    }
    return st.substring(palindromeStart, palindromeEnd + 1);
  }

  public static void main(String[] args) {
    LPS lps = new LPS();
    System.out.println(lps.findLPSLength("abdbca"));
    System.out.println(lps.findLPSLength("cdpdd"));
    System.out.println(lps.findLPSLength("pqr"));
  }
}

[krish]

Thank you.

[David_R_Butler]

Can we add this to the end of the question in the course?

[Caleb1]

Can we have the solution with the top - down approach with memoization(recursion)?

[Austin1]

This is my Kotlin top-down solution for https://leetcode.com/problems/longest-palindromic-substring/

var res = ""

fun longestPalindrome(s: String): String {
    if (s == "") return ""

    val cache = Array(s.length) {
        arrayOfNulls<Int>(s.length)
    }

    val count = dfs(s, cache, 0, s.length - 1)
    return res
}

private fun dfs(st: String, cache: Array<Array<Int?>>, startIndex: Int, endIndex: Int): Int {
    if (startIndex > endIndex)
        return 0
    if (startIndex == endIndex) {
        if (res.length < 1)
            res = st.substring(startIndex, startIndex + 1) // set res
        return 1 // should set res
    }

    if (cache[startIndex][endIndex] == null) {
        if (st[startIndex] == st[endIndex]) {
            val palindromLength = endIndex - startIndex - 1
            if (palindromLength == dfs(st, cache, startIndex + 1, endIndex - 1)) {
                val v = 2 + palindromLength // return cus this is the longest option
                if (v > res.length)
                    res = st.substring(startIndex, startIndex + v) // set res

                cache[startIndex][endIndex] = v
                return v
            }
        }

        val c1 = dfs(st, cache, startIndex + 1, endIndex)
        val c2 = dfs(st, cache, startIndex, endIndex - 1)
        cache[startIndex][endIndex] = Math.max(c1, c2)
    }

    return cache[startIndex][endIndex]!!
}

[nitin]

Here is the java version for returning String. Thanks to Austin1 for sharing his code.

class Solution {
    
    String res="";
    public String longestPalindrome(String s) {
          Integer[][] dp = new Integer[s.length()][s.length()];
        findLPSLengthRecursive(s, 0, s.length() - 1,dp);
       return res; 
  }

  private int findLPSLengthRecursive(String st, int startIndex, int endIndex, Integer[][] dp) {
    if (startIndex > endIndex)
      return 0;

    // every string with one character is a palindrome
    if (startIndex == endIndex){
        if(res==null || res.length()<1)
            res=st.substring(startIndex,startIndex+1);
      return 1;
    }
 if (dp[startIndex][endIndex] == null) {
    // case 1: elements at the beginning and the end are the same
    if (st.charAt(startIndex) == st.charAt(endIndex)) {
      int remainingLength = endIndex - startIndex - 1;
      // check if the remaining string is also a palindrome
      if (remainingLength == findLPSLengthRecursive(st, startIndex + 1, endIndex - 1,dp)){
        int v= remainingLength + 2;
          
        if(v>res.length()){
            res=st.substring(startIndex,startIndex+v);
        }
        
        return  dp[startIndex][endIndex]=v;
      }
    }
 
    // case 2: skip one character either from the beginning or the end
    int c1 = findLPSLengthRecursive(st, startIndex + 1, endIndex,dp);
    int c2 = findLPSLengthRecursive(st, startIndex, endIndex - 1,dp);
     dp[startIndex][endIndex]=Math.max(c1, c2);
     }
      
      return dp[startIndex][endIndex];
  }
}