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