Easy-to-understand Java solution, Time: O(N^2), Space: O(1)


  • 0
    C

    The basic idea is to iterate through each character of the input String and expand left and right if it is a palindrome.

    Time: O(N^2) + O(N^2) = O(N^2)
    Space: O(1)

    public class Solution {
        
        public String longestPalindrome(String s) {
            
            int N = s.length(), maxLength = -1, left = 0, right = 1;
            
            // even length palindromes
            for (int i = 1; i < N; i++) {
                int j = i - 1, k = i;
                while (j >= 0 && k < N && s.charAt(j) == s.charAt(k)) {
                    if (maxLength < k - j) {
                        left = j;
                        right = k + 1;
                        maxLength = k - j;
                    }
                    j--;
                    k++;
                }
            }
            // odd length palindromes
            for (int i = 1; i < N - 1; i++) {
                int j = i - 1, k = i + 1;
                while (j >= 0 && k < N && s.charAt(j) == s.charAt(k)) {
                    if (maxLength < k - j) {
                        left = j;
                        right = k + 1;
                        maxLength = k - j;
                    }
                    j--;
                    k++;
                }
            }
            
            return s.substring(left, right);
        }
    }

Log in to reply
 

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