Java DP solution with optimization in space from O(n^2) to O(n), time O(n^2) with very clear explanations


  • 1

    The original DP solution: time O(n^2), space O(n^2)
    some comments:

    • The outer for-loop's index i goes from n-1 to 0, and the inner for-loop's index j goes from i to n-1, the making i occurs before j, thus we use dp[i][j] to represent if the substring s(i,j) is a palindrome.
    • to check if substring s(i,j) is a palindrome, we first make sure the two characters at s(i) and s(j) equal, then there are two cases to consider:
      • if j - i < 3, which means that the substring's length is less than 3 (e.g. "aba", "ab", "a"), then s(i,j) is a palindrome.
      • if the "inner" substring s(i+1, j-1), without the two characters at s(i) and s(j) is a palindrome, or dp[i+1][j-1], then s(i,j) is a palindrome.
      • when j = 0, j - i is always less than 3, so we never have an index out of bound exception for dp[i+1][j-1]
    • Then we check if dp[i][j] is true, or if s(i,j) is a palindrome, and compare its length with the length of the temporary result, and update the result with the longer one.
    public String longestPalindrome(String s) {
            int n = s.length();
            String result = "";
            boolean[][] dp = new boolean[n][n];
            
            // i goes from n - 1 to 0, j goes from i to n - 1, to make sure i occurs before j
            for (int i = n - 1; i >= 0; i--) {
                for (int j = i; j < n; j++) {
                    dp[i][j] = s.charAt(i) == s.charAt(j) && (j - i < 3 || dp[i+1][j-1]);
                    // if dp[i][j] is true,update result
                    if(dp[i][j] && (result.equals("") || j - i + 1 > result.length())) {
                        result = s.substring(i, j+1); // j+1 not j, since substring includes j
                    }
                }
            }
            return result;
        }
    

    My thoughs on optimization of space complexity:

    We only use dp[i+1][j-1] to update dp[i][j]. We could try reducing the 2D array to 1D array.
    Since the outer for loop is for (int i = n - 1; i >= 0; i--) (the index i has a decreasing order), we could notice that we only need to maintain a 1D array for index j, or using dp[j-1] to update dp[j]. To do so, we need the inner for loop's index j to also go backward from n-1 to i. In this way, when we use dp[j-1] to update dp[j], dp[j-1] is actually the same as 2D array's dp[i+1][j-1], where i+1 is from the last for loop. The reason for index j's decreasing order is to make sure we do not modify the value of dp[j-1] before we use dp[j-1] to update dp[j].

    The optimized DP solution: time O(n^2), space O(n)

    public static String longestPalindrome(String s) {
            int n = s.length();
            String result = "";
            boolean[] dp = new boolean[n];
    
            for (int i = n - 1; i >= 0; i--) {
                for (int j = n - 1; j >= i; j--) { // decreasing order
                    // dp[j-1] is the same as dp[i+1][i-1]
                   // since both dp[j-1] and dp[i+1][j-1] are from the last iteration of the outer loop
                    dp[j] = s.charAt(i) == s.charAt(j) && (j - i < 3 || dp[j-1]);
                    if(dp[j] && (result.equals("") || j - i + 1 > result.length())) {
                        result = s.substring(i, j+1);
                    }
                }
            }
            return result;
        }
    

  • 0
    R

    Nice Solution. Easy to understand.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.