Palindrome substring, palindrome subsequence

409. Longest palindrome ●

describe

Given a string of uppercase and lowercase letters s , return Through these letters Constructed as Of The longest palindrome string .

In the process of construction , Please note that Case sensitive . such as “Aa” Can't be treated as a palindrome string .

Example

Input :
s = “abccccdd”
Output :
7
explain :
The longest palindrome string we can construct is "dccaccd", Its length is 7.

Answer key

1. greedy + Hashtable

The hash table records the number of occurrences of each letter , If it's even , The answer is to add itself , If it's singular , The answer is to add itself and subtract one , And you can put a letter in the middle of the string , So add one to the final answer .

• Time complexity ：$O(N)$, among N For the string s The length of . We need to traverse each character once .
• Spatial complexity ：$O(S)$, among S Is the character set size . The given string is guaranteed in the title s Only upper and lower case letters , So we can also use hash mapping （HashMap） To store the number of occurrences of each character , for example Python and C++ Code for . If you use hash mapping , Only... Will be stored at most 52 individual （ That is, the sum of the number of lower case letters and upper case letters ） Key value pair .

class Solution {
    
public:
    int longestPalindrome(string str) {
    
        int ans = 0, flag = 0;
        unordered_map<char, int> hash;
        for(char ch : str){
    
            ++hash[ch];         //  Count the number of letters 
        }
        for(auto pairs : hash){
    
            if(flag == 0 && pairs.second % 2 != 0){
    
                flag = 1;       //  Odd numbers , You can have a letter in the middle 
            }
            ans += pairs.second % 2 == 0? pairs.second : pairs.second-1;    //  Even numbers are themselves , Odd numbers are themselves -1
        }
        ans += flag;            //  Add the number of letters in the middle 
        return ans;
    }   
};

5. Longest text substring ●●

Give you a string s, find s The longest palindrome substring in .
–
Input ：s = “babad”
Output ：“bab”
explain ：“aba” It's the same answer .

Dynamic planning ideas and 647. Palindrome string ●● similar ;

1. dp[i][j] Express [i, j] Whether the substring in the range is a palindrome string
2. There are three situations in the traversal process , Update the return string when the length is the maximum ans;
   1） There is only one character , It belongs to palindrome string
   2）s[i] != s[j], Non palindrome string
   3）s[i] == s[j], Judge the middle part [i+1, j-1] Whether it is palindrome string （ Only two characters are discussed separately ）
3. dp Initialize to false
4. dp[i][j] May be based on dp[i+1, j-1] Judge , So the starting position of the outer layer i Go back and forth , Inner end position j Traversing from front to back

Time complexity ：$O(n^2)$
Spatial complexity ：$O(n^2)$

class Solution {
    
public:
    string longestPalindrome(string s) {
    
        int len = s.length();
        vector<vector<bool>> dp(len, vector<bool>(len, false));
        int maxL = 1;
        string ans(1, s[0]);
        for(int i = len-1; i >= 0; --i){
        //  The outer layer traverses from back to front 
            dp[i][i] = true;                //  Single character 
            for(int j = i+1; j < len; ++j){
     //  The inner layer is from front to back 
                if(s[i] == s[j]){
               
                    if(j - i == 1){
             //  Two characters 
                        dp[i][j] = true;
                        if(maxL < 2){
           //  Length of judgement 
                            maxL = 2;
                            ans = string(s.begin() + i, s.begin() + j + 1);
                        }
                    }else if(dp[i+1][j-1]){
     // 3 Characters or more , Judge the middle part 
                        dp[i][j] = true;
                        if(maxL < j - i + 1){
       //  Length of judgement 
                            maxL = j - i + 1;
                            ans = string(s.begin() + i, s.begin() + j + 1);
                        }
                    }
                }
            }
        }
        return ans;
    }
};

647. Palindrome string ●●

Give you a string s , Please count and return this string Palindrome string Number of .
Palindrome string Is reading the same string as reading it backwards .
Substring Is a sequence of consecutive characters in a string .
A substring with different start or end positions , Even if it's made up of the same characters , It's also seen as a different substring .
–
Input ：s = “aaa”
Output ：6
explain ：6 Palindrome substrings : “a”, “a”, “a”, “aa”, “aa”, “aaa”

1. Violent traversal

Two layers of for loop , Traverse the starting position and ending position of the interval , Then judge whether this interval is palindrome .

Time complexity ：$O(n^3)$

class Solution {
    
public:
    bool isValid(string s, int start, int end){
         //  Palindrome string   Judge 
        for(int i = 0; i <= (end - start) / 2; ++i){
    
            if(s[start + i] != s[end-i]) return false;
        }
        return true;
    }
    
    int countSubstrings(string s) {
    
        int len = s.length();
        int ans = 0;
        for(int i = 0; i < len; ++i){
               //  With s[i] The first string determines 
            ++ans;
            for(int j = i+1; j < len; ++j){
         //  Traverse to the end 
                if(isValid(s, i, j)) ++ans;     //  Palindrome substring judgment 
            }
        }
        return ans;
    }
};

2. DP

1. dp[i][j] Express [i, j] Substrings in the range Whether it is palindrome string
2. There are three situations in the traversal process ：
   1） There is only one character , It belongs to palindrome string
   2）s[i] != s[j], Non palindrome string
   3）s[i] == s[j], Judge the middle part [i+1, j-1] Whether it is palindrome string （ Only two characters are discussed separately ）
3. dp Initialize to false
4. dp[i][j] May be based on dp[i+1, j-1] Judge , So the starting position of the outer layer i Go back and forth , Inner end position j Traversing from front to back

Time complexity ：$O(n^2)$
Spatial complexity ：$O(n^2)$

class Solution {
    
public:
    int countSubstrings(string s) {
    
        int len = s.length();
        int ans = 0;
        vector<vector<bool>> dp(len, vector<bool>(len, false)); // dp[i][j]  Express [i, j] The substrings in the range are palindromes 
        for(int i = len-1; i >= 0; --i){
            //  The starting position   Go back and forth 
            dp[i][i] = true;        //  Single character 
            ++ans;
            for(int j = i+1; j < len; ++j){
         //  End position   Traversing from front to back 
                if(s[i] == s[j]){
                   //  On the premise that the head and tail are equal 
                    if(j - i == 1){
    
                        dp[i][j] = true;        // 2 Characters , Palindrome 
                        ++ans;
                    }else if(dp[i+1][j-1]){
         // 3 Characters or more , Judge whether there is palindrome in the middle 
                        dp[i][j] = true;
                        ++ans;
                    }
                }   //  Other cases are not palindromes , Do not operate 
            }
        }
        return ans;
    }
};

3. Double pointer （ Center expansion ）

Enumerate all the center points , Then use two pointers to expand to the left and right , When two pointers point to the same element, it expands , Otherwise, stop expanding .

For a string ababa, Choose the middle a As the center point , Spread to both sides , The first diffusion found left Pointing to b,right It also points to b, So it's a palindrome string , Continue to spread , Empathy ababa It's also a palindrome string .

How to enumerate all possible palindrome centers in order , We need to consider two cases where the palindrome length is odd and the palindrome length is even . If the palindrome length is odd , So the palindrome center is A character ; If the palindrome length is even , So the center is Two characters ; So the final center point is 2 * len - 1 individual , Namely len A single character and len - 1 Two characters .

• Time complexity ：$O(n^2)$, Enumerating the palindrome center is $O(n)$ Of , For each palindrome center, the number of expansion is also $O(n)$.
• Spatial complexity ：$O(1)$

Single character and two characters are calculated separately ：

class Solution {
    
public:
    int countSubstrings(string s) {
    
        int ans = 0;
        for(int i = 0; i < s.length(); ++i){
    
            ans += centerCount(s, i, i);	//  Single character centered 
            ans += centerCount(s, i, i+1);	//  Two characters as the center 
        }        
        return ans;
    }

    int centerCount(string s, int left, int right){
          //  Center expansion 
        int ans = 0;
        while(left >= 0 && right < s.length() && s[left] == s[right]){
    
            --left;		//  Two side expansion 
            ++right;
            ++ans;		//  Number  + 1 
        }
        return ans;
    }
};

String center consolidation ：

Traverse 2 * len - 1 A central point ,left = i / 2;right = left + i %2;

class Solution {
    
public:
    int countSubstrings(string s) {
    
        int ans = 0;
        for(int i = 0; i < 2 * s.length() + 1; ++i){
    	//  Traverse 2 * len - 1 A central point 
            int left = i / 2;
            int right = left + i % 2;
            while(left >= 0 && right < s.length() && s[left] == s[right]){
    
                --left;
                ++right;
                ++ans;
            }
        }        
        return ans;
    }
};

4. Manacher Algorithm

• Time complexity ：O(n)
• Spatial complexity ：O(n)

HJ85 Longest text substring ●

describe

Given a Include lowercase letters String , Ask for it The length of the longest palindrome substring .

The so-called palindrome string , Refers to a left-right symmetrical string .
So called substring , Refers to the deletion of some prefixes and suffixes from a string （ It's also possible to delete ） String

Data range ： String length $1\le s\le 350$

Advanced ： Time complexity ：O(n)\O(n) , Spatial complexity ：O(n)\O(n)

Example

Input :
cdabbacc
Output :
4
explain :
abba For the longest palindrome substring

Answer key

ACM Pattern （ Center diffusion & Dynamic programming ）

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int from_center(string &str, int start, int end){
    
    if(str[start] != str[end]){
    
        return 1;
    }
    int ans = end - start + 1;          //  Judge the center length 
    int l = start - 1, r = end + 1;     //  Center expansion 
    while(l >= 0 && r < str.length()){
    
        if(str[l--] != str[r++]) break;
        ans += 2;
    }
    return ans;
}

int main(){
    
    string str;
    while(cin >> str){
    
        int ans = 1, n = str.length();

        // =========== from_center ===========
        // for(int i = 0 ; i < str.length()-1; ++i){
    
        // ans = max(ans, from_center(str, i, i)); //  One letter is the center 
        // ans = max(ans, from_center(str, i, i+1)); //  Centered on two letters 
        // }


        // =============== DP ================
        vector<vector<bool>> dp(n, vector<bool>(n, false));	// dp[i][j]  Express ｛i,j｝ Whether the string in the range is a palindrome 
        for(int i = n-1; i >= 0; --i){
    
            dp[i][i] = true;					//  A single letter , Palindrome 
            for(int j = i+1; j < n; ++j){
    
                if(str[i] != str[j]) break;		//  Whether the head and tail are the same 
                int len = j-i+1;
                if(len == 2){
    					//  The length is 2, Judge palindromes directly 
                    dp[i][j] = true;
                    ans = max(ans, len);
                }else if(dp[i+1][j-1]){
    			//  Longer than 2, Judge whether the middle part is palindrome 
                    dp[i][j] = true;
                    ans = max(ans, len);
                }
            }
        }

        cout << ans << endl;
    }
    return 0;
}

516. The longest palindrome subsequence ●●

Give you a string s , Find the longest Palindrome subsequence , And return the length of the sequence .
Subsequence is defined as ： Without changing the order of the remaining characters , A sequence formed by deleting some characters or not deleting any characters .
–
Input ：s = “bbbab”
Output ：4
explain ： The longest possible palindrome subsequence is “bbbb” .

Palindrome substrings should be continuous , Palindrome subsequences are not continuous ！

1. dp[i][j] Express [i, j] In the substring of the range Number of longest palindrome subsequences
2. There are two cases of traversal ：
   1）s[i] == s[j], be The middle part [i+1, j-1] Length of palindrome subsequence + 2
   dp[i][j] = dp[i+1][j-1] + 2;
   2）s[i] != s[j], choice Go first or Decapitation The length of the longest palindrome subsequence in the substring of .
   dp[i][j] = max(dp[i+1][j], dp[i][j-1]);
3. dp Initialize to 0,dp[i][i] by 1
4. dp[i][j] May be based on dp[i+1, j-1] Judge , So the starting position of the outer layer i Go back and forth , Inner end position j Traversing from front to back

Time complexity ：$O(n^2)$
Spatial complexity ：$O(n^2)$

class Solution {
    
public:
    int longestPalindromeSubseq(string s) {
    
        int len = s.length();
        vector<vector<int>> dp(len, vector<int>(len, 0));
        for(int i = len - 1; i >= 0; --i){
    	//  Starting position of outer layer  i  Go back and forth 
            dp[i][i] = 1;
            for(int j = i+1; j < len; ++j){
    	//  Inner end position  j  Traversing from front to back 
                if(s[i] == s[j]){
    
                    dp[i][j] = dp[i+1][j-1] + 2;	//  Remove the length of palindrome subsequence at the beginning and end  + 1
                }else{
    
                    dp[i][j] = max(dp[i+1][j], dp[i][j-1]);	//  choice   Go first   or   Decapitation 
                }
            }
        }
        return dp[0][len-1];	//  Range the longest subsequence length in the whole string range 
    }
};