LeetCode LintCode C++ English Version 2 pointers medium

Leetcode 5. Longest Palindromic Substring

Lintcode 200. Longest Palindromic Substring

Posted by Olivia Liu on August 14, 2019 | 阅读：次

Description

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Answer

The main idea is basically the same with valid palindrome, which is determine if a string is palindromic by using 2 pointers.

Code

C++

class Solution {
public:
    string longestPalindrome(string s) {
        if(s.length() <= 1) return s;
        string str = "", ans = "";
        int maxl = -1, cnt = 0;
        int n = s.length();
        for(int i = 0; i < n; ++i)
        {
            str += '#';
            str += s[i];
        }
        str += '#';
        for(int i = 1; i < 2 * n; ++i)
        {
            cnt = 0;
            while((i - cnt >= 0) && (i + cnt <= 2 * n) && (str[i - cnt] == str[i + cnt])) cnt++;
            cnt--;
            if(cnt > maxl)
            {
                maxl = cnt;
                ans = s.substr((i - cnt) / 2, (i + cnt) / 2 - (i - cnt) / 2);
            }
        }
        return ans;
    }
};