【上分日记】第378场周赛(分类讨论 + 分组循环 + 前缀和)

前言

?这场周赛博主勉强算是写出了3道题，“勉强” 就在于 第3道题没在规定时间内写出来，但还是自己单独想
出来了，还算是有一点进步 ( hhh, 菜鸡勿喷 )。下面博主把这两道题再总结一下。

正文

1. 2982. 找出出现至少三次的最长特殊子字符串 II

• 题目链接:2982. 找出出现至少三次的最长特殊子字符串 II

• 再多bb两句，这道题在做的时候因为数据量太大，暴力是做不出来的，博主先想到了分组循环，然后又想到了滑动窗口，接着又想到了堆，又开始观察分类讨论分析规律，最后时间不够了，做题的心路历程真是曲折的一批。

---

• 题目思路：

1. 我们先得对每一个连续的特殊子字符串，求长度，然后进行分组。

1. 在实现过程中，当前一个字符与前一个字符不匹配时，当前的特殊字符串的长度就求完了，就可以扔到对应的组里面，这里我们以直接用unoredered_map进行求解，也可以用一个26个元素的vector进行求解, 然后接着循环。
2. 分组时，我们还可以用一个小根堆进行优化，因为至少出现3次，且要取最长的长度，也就是在前3个最大的长度中求可以取3个特殊字符串的最长的长度，因此我们可以用一个3个元素的小根堆维护前3大个数即可。

• 此处可能会出现堆中元素小于3个的情况，我们可以放两个0，来让其达到3个，进而方便求解。

2. 每一组取出最长的前3个元素，进行分类讨论可以取得3个特殊字符串的最大长度。

• 因为至少取得这3个特殊字符串的最大长度，只可能在这3个元素中出现，那么我们对这3个元素分别进行讨论即可。

1. 设这3个元素分别为 n1（最长）， n2(次长)，n3（较长）
2. 假设最长的是n3, 则一定能取到 3 个长度为 n3的 特殊子字符串。
3. 假设最长的是n2, 则 n1 - n2 <= 1

1. 如 果 n2 == n1, 则取 n2 - 1。
2. 如果 n1 == n2 + 1, 则取 n2

4. 假设最长的是n1,则 n1 - n2 >= 2, 则取 n1 - 2。

• 取这些情况的最大值即可。
• 理解方式：可以取长度为len的子串，进行滑动看能在n1,n2,n3中取几个。

• 实现代码：

class Solution {
public:
    int maximumLength(string s) 
    {
          //将所有的相同的特殊子字符串都分组并进行划分，并求出其长度。
          unordered_map<char,priority_queue<int,vector<int>,greater<int>>> hash;
          int sz = s.size(),begin = 0;
          for(int i = 0; i <  sz; i++)
          {
              if(i + 1 == sz || s[i] != s[i + 1])
              {
                  int len = i + 1 - begin;
                  //维护一个堆为3的小根堆
                  if(hash[s[i]].size() < 3)
                  {
                    hash[s[i]].push(len);
                  }
                  else
                  {
                      //等于3时我们只需与堆顶元素进行比较如果大就入堆即可
                      int top = hash[s[i]].top(); hash[s[i]].pop();
                      //将最大值再入堆即可
                      hash[s[i]].push(max(top,len));
                  }
                  begin = i + 1;
              }
          }
          int ans = 0;
          for(int i = 'a'; i <= 'z'; i++)
          {
              //需要判断一下队列不为空
              if(!hash[i].empty())
              {
                //防止只有一个的情况
                if(hash[i].size() < 3)
                    hash[i].push(0);
                if(hash[i].size() < 3)
                    hash[i].push(0);
                int n3 = hash[i].top(); hash[i].pop();
                int n2 = hash[i].top(); hash[i].pop();
                int n1 = hash[i].top(); hash[i].pop();
                //对第三长的和第二长的以及第一长的取最长的字符串进行分类讨论。
                int len3 = n3;//一定能取到

                int len2 = 0;
                if(n1 == n2) // 相等取n2-1
                    len2 = n2 - 1;
                else if(n1 - n2 == 1) //差1取n2
                    len2 = n2;

                int len1 = 0;
                if(n1 - n2 >= 2)// 差2取 n1 - 2
                    len1 = n1 - 2;
                    
                int len = max(len3,max(len1,len2));
                ans = max(ans,len);
              }
          }         
          return ans == 0 ? -1 : ans;
    }
};

2.2983. 回文串重新排列查询

• 题目链接：2983. 回文串重新排列查询

---

• 题目大致思路：

1. 因为要查询，且要将字符串分为两部分进行，然后再各取一部分排列组合，看是否能组成回文串。

2. 因此我们直接将字符串分成两部分，然后再对第二部分逆转，这样就转换为了分别取字符串的一部分，取的一部分可以随意排列组合，看字符串之间能否互相转换。

3. 我们可以将区间大致分为两部分，能进行排列的部分，和不能进行排列的部分。

4. 能进行排列的部分看是否能转换为对应的字符串，不能转换的部分看是否相等即可。

5. 我们可以使用前缀和，即对26种字符分别求前缀和，这样就可得到指定区间的字符个数，只要指定区间的字符个数都相等，则对应部分可以进行互相转换，反之则不能。 两个字符串都要求，因此有52个前缀和。

6. 我们还可以使用前缀和，即判断两个原始字符串的每个字符串是否相等，如果相等就为0，不等就为1，并对此求前缀和，这样我们就可以快速判断某一段区间的字符串是否相等，即如果为0则相等，如果为1则不相等。 这里有1个前缀和，总共53个前缀和。

7. 我们再进行分类讨论，对应的具体情况有6种，有3种可以互相转换，因此我们可以优化一下。具体情况请看实现代码，并建议画图分析。

• 实现代码：

class Solution {
public:

    vector<bool> canMakePalindromeQueries(string s, vector<vector<int>>& queries) 
    {
        //1.预处理，方便对数据进行处理
        int len = s.size();
        string s1 =  s.substr(0,len / 2);
        string s2 =  s.substr(len / 2, len / 2);
        reverse(s2.begin(),s2.end()); 
        int len1 = s1.size(); 
        auto get_range = [&](int i)->pair<int,int>
        {
            int len2 = s2.size();
            int ci = queries[i][2],di = queries[i][3];
            int begin = len2 - 1 - (ci - len / 2);
            int end = len2 - 1 - (di - len / 2);
            return {min(begin,end), max(begin,end)};
        };
        /*
            1.细节：题目中给出长度一定为偶数，因此s1和s2的长度必然相等
            2.逆转是为了方便进行正向对比。
                注意：此时对于s[ci : di]在s2的下标会有所变化。
                未反转的s2:   ci-> ci - len / 2 , di->di - len / 2;
                翻转之后的s2: [ min{s2.size()-1 - ci , s2.size() - di},
                max{s2.size()-1 - ci, s2.size() - di} ];
                //对称的性质: x1 + x2 = s2.size() - 1;
        */
        //2.求出26 + 26 + 1个前缀和方便进行查询
        vector<vector<int>> ch1_que(26,vector<int>(len1 + 1,0)),ch2_que(ch1_que);
        for(int i = 0; i < 26; i++)
        {
            for(int j = 1; j <= len1; j++)
            {
                ch1_que[i][j] = s1[j-1] - 'a' == i ? ch1_que[i][j-1] + 1 : ch1_que[i][j-1];
                ch2_que[i][j] = s2[j-1] - 'a' == i ? ch2_que[i][j-1] + 1 : ch2_que[i][j-1];
            }
        }
        /*
           求出每一段对应的每种字母出现的次数，且只有26个小写字母，方便后面的大量查询。 
        */
        vector<int> dif(len1 + 1,0);
        for(int i = 1; i <= len1; i++)
        {
            dif[i] = s1[i-1] == s2[i-1] ? dif[i-1] : dif[i-1] + 1;                
        }
        /*
            异或前缀和:快速判断某段区间是否相等，如果相等就是可能构成回文串，因为我们已经对s2做了逆转。
            此处用于对不进行排列的区间的快速判断。
        */

        //3.分类进行讨论
        function<bool(int,int)> count = [&](int begin,int end)->bool
        {
            //[begin,end]
            for(int i = 0; i < 26; i++)
            {
                if(ch1_que[i][end + 1] - ch1_que[i][begin] !=
                 ch2_que[i][end + 1] - ch2_que[i][begin])
                {
                    return false;
                }
            }
            return true;
        };
        auto check = [&](int l1,int r1,int l2,int r2,string& s1,string& s2,\
        vector<vector<int>>& ch1_que,vector<vector<int>>&ch2_que)->bool
        {
            //保证l1 <= l2 会有3种情况。
            //先处理两边必然不相交的，因此先判断 [0,l1), [r2+1,len1)的字符串是否匹配。
            //细节：求的前缀和是不包含当前顶点的。
            int right = max(r1 + 1,r2 + 1);
            if(dif[l1] || (dif[len1] - dif[right]))
            {
                return false;
            }
            //先处理不相交的情况
            if(l2 > r1)
            {
                //先判断中间[r1 + 1,l2)的字符串是否匹配.
                if(dif[l2] - dif[r1 + 1])
                {
                    return false;
                }
                //计算s1[l1,r1]的种类个数能否与s2[l1,r1]的种类个数匹配
                if(count(l1,r1) && count(l2,r2))
                {
                    return true;
                }
                return false;
            }
            //再处理包含的情况
            if(r1 >= r2)
            {
                if(count(l1,r1))
                {
                    return true;
                }
                return false;
            }
            //最后处理相交但不包含的情况
            if(r1 >= l2)
            {
                //1. 先让[l1,r1]去匹配[l1,l2]
                int tmp1[26] = {0};
                for(int i = 0; i < 26; i++)
                {
                    int sub = ch1_que[i][r1 + 1] - ch1_que[i][l1] - 
                    (ch2_que[i][l2] - ch2_que[i][l1]);
                    if(sub < 0) return false;
                    else 
                    {
                        tmp1[i] = sub;
                    }
                }
                //2. 再让[l2,r2] 去匹配[r1 + 1,r2]
                int tmp2[26] = {0};
                for(int i = 0; i < 26; i++)
                {
                    int sub = ch2_que[i][r2 + 1] - ch2_que[i][l2] - 
                    (ch1_que[i][r2 + 1] - ch1_que[i][r1 + 1]);
                    if(sub < 0) return false;
                    else
                    {
                        tmp2[i] = sub;
                    }
                }
                //最后看[l2,r1] 即tmp1 和 tmp2 是否匹配
                for(int i = 0; i < 26; i++)
                {
                    if(tmp1[i] != tmp2[i])
                        return false;
                }
            }
            return true;
        };
        int qsz = queries.size();
        vector<bool> ans(qsz);
        for(int i = 0; i < qsz; i++)
        {
            int l1 = queries[i][0];
            int r1 = queries[i][1];
            pair<int,int> ret = get_range(i);
            int l2 = ret.first;
            int r2 = ret.second;
            //这一步很关键,可以将6种情况转换为3种情况。
            ans[i] = l1 <= l2 ? check(l1,r1,l2,r2,s1,s2,ch1_que,ch2_que) 
            : check(l2,r2,l1,r1,s2,s1,ch2_que,ch1_que);
        }
        return ans;
    }
};

• 说明：本题的思路参考灵神的思路实现，详细内容可见灵神在b站的周赛回放视频。

总结

1. 第一题，用unordered_map 或者 vector 可以将特殊字符串的所有长度进行分组，然后对其进行分类讨论，对3种情况进行讨论即可。(哈希分组循环 + 分类讨论 + priority_queue小优化——感觉优化了个寂寞)
2. 第二题，可以说是将前缀和用的淋漓尽致，从而可以快速的判断是否可以组成回文串，且如果有重复的对称的情况，这里将6种情况转换为3种情况，从而减少代码量。(53个前缀和 + 问题转换 + 分类讨论)

尾序

? 我是舜华，期待与你的下一次相遇！