competitive-programmingNov 1, 20211 min read

[LeetCode] 5. Longest Palindromic Substring Explained

Updated: Nov 1, 2021

Dynamic programming

Available in:enko

#Problem

5. Longest Palindromic Substring

#Approach

Consider the palindrome formed by adding a single character to a palindrome of length $l$ : its length is either $l+1$ or $l+2$ .
But if the longest palindrome I already know has length $l$ , there is no need to even check for the existence of palindromes of length $l$ or less.
For each character $s[i]$ , we only need to search whether there is a palindrome of length $l+1$ or $l+2$ that ends with that character.

#Code

/**
 * author: jooncco
 * written: 2021. 10. 31. Mon. 00:30:16 [UTC+9]
 **/

class Solution {
private:
    bool isPalindrome(string str) {
        int n= str.length();
        for (int i=0; i < n/2; ++i) {
            if (str[i] != str[n-1-i]) return 0;
        }
        return 1;
    }

public:
    string longestPalindrome(string s) {
        int n= s.length();
        int idx= 0, len= 0;
        for (int i=0; i < n; ++i) {
            if (isPalindrome(s.substr(i-len, len+1))) {
                idx= i-len;
                len += 1;
            }
            else if (i-len > 0 && isPalindrome(s.substr(i-len-1, len+2))) {
                idx= i-len-1;
                len += 2;
            }
        }
        return s.substr(idx,len);
    }
};

#Complexity

Time: $O(\vert s \vert)$
Space: $O(1)$