Using longest common substring approach (Java)


  • 0
    C

    I tried to solve the problem using a slightly modified algorithm of longest common substring between original string and reverse of original string. But the algorithm is exceeding time limit esp for input "aaaa......aaa" (length 1000). Any ideas on how I could improve this algorithm?

    The extra logic I have in place is to make sure "substring’s indices are the same as the reversed substring’s original indices" to guarantee the longest substring is a palindrome.

    public class Solution {
        public String longestPalindrome(String s) {
            if (s == null || s.length() == 0) {
                return "";
            }
    
            int[][] lcs = new int[s.length()][s.length()];
            int maxLength = 0;
            int finalStartPos = 0;
            for (int i=0; i < s.length(); i++) {
                for (int j=0; j < s.length(); j++) {
                    
                    if (s.charAt(i) == s.charAt(s.length() - j - 1)) {
                        if (i-1 >= 0 && j-1 >= 0)    {
                            lcs[i][j] = lcs[i-1][j-1] + 1;
                        } else {
                            lcs[i][j] = 1;
                        }
                        
                        int startPosX = i - (lcs[i][j] - 1);
                        int endPosY = j - (lcs[i][j] - 1);
                        
                        if (lcs[i][j] > maxLength && s.length() - (startPosX + lcs[i][j]) == endPosY) {
                            maxLength = lcs[i][j];
                            finalStartPos = startPosX;
                        }
                    }
                }
            }
    
            return s.substring(finalStartPos, finalStartPos + maxLength);
        }
        
    }
    

Log in to reply
 

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