educative.io

Educative

Return String instead of length

Hi,

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

Thanks,
Krishna.

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"));
  }
}
2 Likes

Thank you.

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

1 Like

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

1 Like

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]!!
}
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];
  }
}