Hello, everyone, I’m Coding bear, today is the fifth day of LeetCode daily problem, let’s learn LeetCode fifth problem “longest reply substring”.

The question

Given a string s, find the longest echo substring in S.

The sample

Input: s = "babad" Output: "bab" Explanation: "aba" is also a correct answer.Copy the code

Answer key

Methods a

Using a simple and violent method, enumerate each position as a single palindrome center (odd length substring, such as ABA) or one of the palindrome centers (even length substring, such as ABBA), and expand left and right to see if they are equal until they are not equal or stop expanding at the beginning/end of the string. In the worst case, such as aaaAAA, the time complexity is O(n2)O(n^2)O(n2).

/ / c + + code
class Solution {
public:
    string longestPalindrome(string s) {
        int st = 0, ed = 0;
        for (int i = 0; i < s.size(a); i++) {auto ans1  = expandMaxLen(s, i, i);
            auto ans2  = expandMaxLen(s, i, i + 1);
            if (ans1.second - ans1.first > ed - st) {
                ed = ans1.second;
                st = ans1.first;
            }
            if(ans2.second - ans2.first > ed - st) { ed = ans2.second; st = ans2.first; }}return s.substr(st, ed - st +  1);
    }
    pair<int.int>  expandMaxLen(string s, int l, int r) {
        while (l >= 0 && r < s.size() && s[l] == s[r]) {
            --l;
            ++r;
        }
        pair<int.int> ans = {l + 1, r - 1};
        returnans; }};Copy the code

Time complexity: O(n2)O(n^2)O(n2)

Space complexity: O(n)O(n)O(n)

Method 2

The Manacher algorithm can find the longest substring of a string in the time complexity of O(n)O(n)O(n). There will be a whole article about Manacher algorithm later.

The following code is the solution of Manacher algorithm, the code is more than 99.9% of the solution, you can understand first.

Time complexity: O(n)O(n)O(n)

Space complexity: O(n)O(n)O(n)

Summary of knowledge point: enumeration, Manacher algorithm.

C + + code

class Solution {
public:
    string longestPalindrome(string s) {
        string str = preSovle(s);
        int max_id = 0, max_pos = 0, ans_pos, ans_len = 0;
        vector<int> arm_len(str.size(), 0);
        for (int i = 2; i <= str.size() - 2; i++) {
            if (max_pos > i) arm_len[i] = min(max_pos - i, arm_len[2 * max_id - i]);
            else arm_len[i] = 1;
            while (str[i + arm_len[i]] == str[i - arm_len[i]]) arm_len[i]++;
            if (i + arm_len[i] > max_pos) {
                max_pos = i + arm_len[i];
                max_id = i;
            }
            if (arm_len[i] - 1 > ans_len) {
                ans_len = arm_len[i] - 1; ans_pos = i; }}int pos = (ans_pos - 2) / 2;
        return str[ans_pos] == The '#' ? s.substr(pos - ans_len / 2 + 1, ans_len):
                                     s.substr(pos - ans_len / 2, ans_len);
    }
    string preSovle(string s) {
        string str = "$";
        for (int i = 0; i < s.size(a); i++) { str +=The '#';
            str += s[i];
        }
        str += The '#', str += The '*';
        returnstr; }};Copy the code

Java code

class Solution {
    public String longestPalindrome(String s) {
        String str = preSolve(s);
        int max_id = 0, max_pos = 0, ans_pos = 0, ans_len = 0;
        int[] arm_len = new int[str.length()];

        for (int i = 2; i <= str.length() - 2; i++) {
            if (max_pos > i) arm_len[i] = Math.min(max_pos - i, arm_len[2 * max_id - i]);
            else arm_len[i] = 1;
            while (str.charAt(i + arm_len[i]) == str.charAt(i - arm_len[i])) arm_len[i]++;
            if (i + arm_len[i] > max_pos) {
                max_pos = i + arm_len[i];
                max_id = i;
            }
            if (arm_len[i] - 1 > ans_len) {
                ans_len = arm_len[i] - 1; ans_pos = i; }}int pos = (ans_pos - 2) / 2;
        return str.charAt(ans_pos) == The '#' ? s.substring(pos - ans_len / 2 + 1, pos - ans_len / 2 + ans_len + 1):
            s.substring(pos - ans_len / 2, pos - ans_len / 2 + ans_len);
    }

    public String preSolve(String s) {
        String str = "$";
        for (int i = 0; i < s.length(); i++) {
            str = str.concat("#");
            str += s.charAt(i);
        }
        str += The '#';
        str += The '*';
        returnstr; }}Copy the code

Title link: https://leetcode-cn.com/problems/longest-palindromic-substring/

I am a programming bear, continue to output LeetCode problems, dafang interview, dafang reliable point to point to push related content, focus on “a programming bear”, get information!

Welcome to “follow”, “like”, “retweet” support ~