Sword finger offer special assault edition day 6

The finger of the sword Offer II 017. The shortest string containing all characters
hard topic （ Time beats 100%）
Double pointer （ $j$ Used to extend string ,$i$ Used to shorten the string ）, Time complexity $O(n)$

class Solution {
    
public:
    string minWindow(string s, string t) {
    
        int n = s.size(), m = t.size();
        int len = 0x3f3f3f3f;
        string res;
        
        int tst[200] = {
    0}; // Mark the number of characters separately  
        int tcnt = 0; // Different number of characters  
        for(int i = 0; i < m; i++) {
    
            if(!tst[t[i]]) tcnt++;
            tst[t[i]]++;
        }
        
        int sst[200] = {
    0}; // Mark the number of characters separately 
        bool st[200] = {
    0}; // Mark s The substring has been greater than or equal to t The characters in  
        int i = 0, j = 0, scnt = 0; //scnt by st The array is true The number of  
        while(j < n) {
    
            if(tst[s[j]] != 0) {
    
                stst[s[j]]++;
                if(!st[s[j]] && sst[s[j]] >= tst[s[j]]) {
    
                	scnt++;
                	st[s[j]] = true;
				}
            }
            
            if(scnt == tcnt) {
     
            	//s The substring contains t All the characters in , Start moving i To reduce the length of the substring  
                while(!tst[s[i]] || stst[s[i]] - 1 >= tst[s[i]]) {
    
                    stst[s[i++]]--;
                }
                if(len > j-i+1) {
    
                    len = j-i+1;
                    res = s.substr(i,len);
                }
            }

            j++;
        }
        return  res;
    }
};

The finger of the sword Offer II 018. Valid palindromes
Simple palindrome string

class Solution {
    
public:
    bool isPalindrome(string s) {
    
        int n = s.size();
        string tmp;
        
        for(char c : s) {
    
            if(c >= '0' && c <= '9') tmp += c;
            else if(c >= 'a' && c <= 'z') tmp += c;
            else if(c >= 'A' && c <= 'Z') tmp += (char)(c+32);
        }

        n = tmp.size();
        for(int i = 0; i < n/2; i++) 
            if(tmp[i] != tmp[n-i-1]) 
                return false;

        return true;
    }
};

The finger of the sword Offer II 019. Delete at most one character to get a palindrome

It is more complicated than ordinary palindrome strings , Good writing abstracts and separates redundant modules

class Solution {
    
public:
    bool check(string &s, int l,int r) {
    
        while(l < r) {
    
            if(s[l] != s[r]) return false;
            else l++,r--;
        }
        return true;
    }
    bool validPalindrome(string s) {
    
        int i = 0, j = s.size()-1;
        int idx1 = -1, idx2 = -1;
        while(i < j) {
    
            if(s[i] == s[j]) {
     
                i++,j--;   
            } else {
    
                return check(s,i+1,j) || check(s,i,j-1);
            }
        }
        return true;
    }
};

The finger of the sword Offer II 020. Number of palindrome substrings
character string +DP

$O(n^2)$ practice

class Solution {
    
public:
    int countSubstrings(string s) {
    
        int n = s.size();
        int cnt = 0;
        bool st[1010][1010] = {
    0};
        for(int i = 0; i < n; i++) {
    
            st[i][i] = true; cnt++;
            for(int j = 0; j < i; j++){
    
                if(s[j] == s[i]) {
    
                    if(i-j+1 > 2 && st[j+1][i-1] != true) continue;
                    cnt++, st[j][i] = true;    
                }
            }
        }
        return cnt;
    }
};

$O(n)$dp practice
Reference resources ：https://leetcode.cn/problems/a7VOhD/solution/hui-wen-zi-zi-fu-chuan-de-ge-shu-by-leet-ejfv/

class Solution {
    
public:
    int countSubstrings(string s) {
    
        int n = s.size();
        string t = "$#";
        for (const char &c: s) {
    
            t += c;
            t += '#';
        }
        n = t.size();
        t += '!';

        auto f = vector <int> (n);
        int iMax = 0, rMax = 0, ans = 0;
        for (int i = 1; i < n; ++i) {
    
            //  initialization  f[i]
            f[i] = (i <= rMax) ? min(rMax - i + 1, f[2 * iMax - i]) : 1;
            //  Center expansion 
            while (t[i + f[i]] == t[i - f[i]]) ++f[i];
            //  Dynamic maintenance  iMax  and  rMax
            if (i + f[i] - 1 > rMax) {
    
                iMax = i;
                rMax = i + f[i] - 1;
            }
            //  Statistical answer ,  The current contribution is  (f[i] - 1) / 2  Round up 
            ans += (f[i] / 2);
        }

        return ans;
    }
};