LeetCode 5. Longest Palindromic Substring

Problem:

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

Solution:

public class Solution {
    int pos, max;
    
    public String longestPalindrome(String s) {
        if (s.length() < 2) return s;
        for (int i = 0; i < s.length() - 1; i++) {
            extend(s, i, i);
            extend(s, i, i + 1);
        }
        return s.substring(pos, pos + max);
    }
    
    private void extend(String s, int low, int high) {
        while (low >= 0 && high < s.length() && s.charAt(low) == s.charAt(high)) {
            low--;
            high++;
        }
        if (high - low - 1 > max) {
            max = high - low - 1;
            pos = low + 1;
        }
    }
}

Leave a Reply

Your email address will not be published. Required fields are marked *