Resolved TLE | Java solution | DP | O(n^2)


  • 0
    M
    public class Solution {
        public String longestPalindrome(String s) {
            
            char[] cArr = s.toCharArray();
            int len = cArr.length;
            
            boolean[][] dp = new boolean[len][len];
            
            int maxLen = Integer.MIN_VALUE, currLen = 1;
            String longestPallindromicStr = "";
            
            // 1-length pallindromic substrings
            for (int i = 0; i < cArr.length; i++) {
                
                dp[i][i] = true;
                maxLen = 1;
                longestPallindromicStr = String.valueOf(cArr[i]);
            }
            
            // 2-length pallindromic substrings
            for (int i = 0; i < len - 1; i++) {
                
                if (cArr[i] == cArr[i + 1]) {
                    
                    dp[i][i + 1] = true;
                    
                    if (maxLen < 2) {
                        maxLen = 2;
                        longestPallindromicStr = "" + cArr[i] + cArr[i + 1];
                    }                
                    
                } else {
                    dp[i][i + 1] = false;
                }
            }
            
            // 3 or more length pallindromic substrings
            for (int subLen = 2; subLen < len; subLen++) {
                
                for (int i = 0; i < len - subLen; i++) {
                    
                    int j = i + subLen;
                    
                    if (cArr[i] == cArr[j] && dp[i+1][j-1]) {
                        
                        dp[i][j] = true;
                        
                        if (subLen + 1 > longestPallindromicStr.length()) {
                            longestPallindromicStr = s.substring(i, j + 1);
                        }
                    } else {
                        dp[i][j] = false;
                    }
                }            
            }        
            return longestPallindromicStr;        
        }
    }
    

Log in to reply
 

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