Leetcode-1156 Swap For Maximum Repeated Substring(单字符重复子串的最大长度)

╰半橙微兮° 2023-06-01 08:48 61阅读 0赞

因为只能交换一次，先考虑如果不交换最大的值。

接下来考虑交换，有四种情况

① aaabaaa型 交换一下可以将相邻的两块连在一起，答案就是两块长度之和

② aaabbbaaaa 交换一下也不能连起两块，答案就是最长的长度加一

③ aaab 没有可以交换的，答案就是不交换的长度

④ aaabaaaaba型 交换一下不但可以将相邻的两块连在一起，甚至中间的连接点还是相邻两块的那个字母，答案就是两块长度之和加一

1 #define _for(i,a,b) for(int i = (a);i < b;i ++)
     2 
     3 
     4 class Solution
     5 {
     6     public:
     7         int check(string &s,int st)
     8         {
     9             int rnt = 1;
    10             _for(i,st+1,s.size())
    11                 if(s[i]!=s[i-1])
    12                     break;
    13                 else
    14                     rnt ++;
    15             return rnt;
    16         }
    17         int maxRepOpt1(string text)
    18         {
    19             int hash[30];
    20             int kuai[30];
    21             memset(hash,0,sizeof(hash));
    22             memset(kuai,0,sizeof(kuai));
    23             _for(i,0,text.size())
    24             {
    25                 int len = check(text,i);
    26                 hash[text[i]-'a'] = max(hash[text[i]-'a'],len);
    27                 kuai[text[i]-'a'] ++;
    28                 i += len-1;
    29             }
    30             int rnt = 0;
    31             _for(i,0,29)
    32                 rnt = max(rnt,hash[i]);
    33             
    34             _for(i,0,text.size())
    35             {
    36                 int len = check(text,i);
    37                 if(i+len+1<text.size() && text[i+len+1]==text[i])
    38                 {
    39                     int len2 = check(text,i+len+1);
    40                     rnt = max(rnt,len+len2);
    41                     if(kuai[text[i]-'a']>2)
    42                         rnt = max(rnt,len+len2+1);
    43                 }
    44                 if(kuai[text[i]-'a']>1)
    45                     rnt = max(rnt,len+1);
    46                 i += len-1;
    47             }
    48             return rnt;
    49         }
    50 };

转载于:https://www.cnblogs.com/Asurudo/p/11334560.html