Share my naive O(n^2) Java solution (beats 82.11%)


  • 0
    M

    -- the idea is simple: just expand from one center to see how far it can go

    -- iterate through all centers

    -- note that for each center/expansion, the length of palindromic substring can be odd or even.

    public class Solution {
        public String longestPalindrome(String s) {
            int from = 0, to = 0;
            for (int i = 0; i < s.length(); ++i) {
                int[] oddLenResult = expandFromCenter(s, i - 1, i + 1);
                if (oddLenResult[1] - oddLenResult[0] > to - from) {
                    from = oddLenResult[0];
                    to = oddLenResult[1];
                }
                int[] evenLenResult = expandFromCenter(s, i, i + 1);
                if (evenLenResult[1] - evenLenResult[0] > to - from) {
                    from = evenLenResult[0];
                    to = evenLenResult[1];
                }
            }
            return s.substring(from, to);
        }
        
        private int[] expandFromCenter(String s, int left, int right) {
            int p = left, q = right;
            while (p >= 0 && q < s.length() && s.charAt(p) == s.charAt(q)) {
                --p;
                ++q;
            }
            return new int[] {p + 1, q};  // s.substring(p + 1, q) is the current longest palindromic substring
        }
    }

Log in to reply
 

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