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

发布时间 2024-01-03 11:32:50作者: .Ivorelectra

开26个multiset,对于aabaaa,遍历,对第0个multiset push 1 2,然后对第一个multiset push 1,然后又对第0个multiset push 1 2,这时第0个multiset size超过3了,删除最小的元素,然后继续push 3,最后取 \(max_{i=1}^{26}(*multiset_{i}.begin())\)。过程就是维护每个multiset的size不超过3,对于一个multiset中有1 2 3,就表示有3个1,2个2,1一个3,1看起来只记录的1次,但是有2和3说明1有3次,同理2看起来只记录了一次,但是有3说明2有2次,所以每次size超过3时删除multiset中最小的元素。

class Solution {
public:
    int maximumLength(string s) {
        multiset<int> st[30];
        char c = s[0];
        int cnt = 0;
        for(int i = 0; i < s.size(); ++i)
        {
            if(s[i] != c)
            {
                cnt = 1;
                c = s[i];
                st[s[i]-'a'].insert(cnt);
            }
            else
            {
                cnt++;
                st[s[i]-'a'].insert(cnt);
            }
            if(st[s[i]-'a'].size() > 3) st[s[i]-'a'].erase(st[s[i]-'a'].begin());
        }
        int ans = -1;
        for(int i = 0; i < 26; ++i)
        {
            if(st[i].size() == 3)
            {
                ans = max(ans, *st[i].begin());
                //cout << i << ' ' << *st[i].begin() << endl;
            }
        }
        return ans;
    }
};