C ++中最短的多数子字符串

假设我们有一个小写字母字符串s，我们必须找到最短子字符串的长度（最小长度为2），以使某个字母比其他字母组合在一起的出现更多。如果找不到任何解决方案，则返回-1。

因此，如果输入类似于“ abbbcde”，则输出将为2，子字符串“ bb”的长度最小，并且比其他字母更长。

为了解决这个问题，我们将遵循以下步骤-

• 定义一个函数ok()，它将使用一个数组cnt，

• 总计：= 0，maxVal：= 0

• 对于cnt中的每个元素，执行

• 总计：=总计+它

• maxVal：= maxVal及其最大值

• 当maxVal>(total-maxVal)时返回true

• 从主要方法中，执行以下操作-

• n：= s的大小

• ret：= inf

• 对于初始化i：= 0，当i <n时，更新（将i增加1），执行-

• ret：= 3

• 返回2

• 如果i +1 <n并且s [i]与s [i +1]相同，则-

• 否则，当i + 2 <n并且s [i]与s [i + 2]相同时，则-

• 返回（如果ret与inf相同，则为-1，否则为ret）

让我们看下面的实现以更好地理解-

示例

 现场演示

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   bool ok(vector <int>& cnt){
      int total = 0;
      int maxVal = 0;
      for(auto& it : cnt){
         total += it;
         maxVal = max(maxVal, it);
      }
      return maxVal > (total - maxVal);
   }
   int solve(string s) {
      int n = s.size();
      int ret = INT_MAX;
      for(int i = 0; i < n; i++){
         if(i + 1 < n && s[i] == s[i + 1]){
            return 2;
         }else if(i + 2 < n && s[i] == s[i + 2]){
            ret = 3;
         }
      }
      return ret == INT_MAX ? -1 : ret;
   }
};
int main(){
   Solution ob;
   cout << (ob.solve("abbbcde"));
}

输入值

"abbbcde"

输出结果

2