Chuỗi con đa số ngắn nhất trong C ++

Giả sử chúng ta có một chuỗi chữ cái viết thường s, chúng ta phải tìm độ dài của chuỗi con ngắn nhất (độ dài tối thiểu là 2) sao cho một số chữ cái xuất hiện nhiều hơn các chữ cái khác cộng lại. Nếu chúng tôi không thể tìm thấy bất kỳ giải pháp nào, hãy trả về -1.

Vì vậy, nếu đầu vào là "abbbcde", thì đầu ra sẽ là 2, chuỗi con "bb" có độ dài tối thiểu và ký tự này xuất hiện nhiều hơn các chữ cái khác.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định một hàm ok (), điều này sẽ lấy một mảng cnt,

• tổng:=0, maxVal:=0

• đối với mỗi phần tử nó trong cnt, thực hiện

  • tổng:=tổng + nó

  • maxVal:=tối đa của maxVal và nó

• trả về true khi maxVal> (total - maxVal)

• Từ phương thức chính, thực hiện như sau -

• n:=kích thước của s

• ret:=inf

• để khởi tạo i:=0, khi i

  • nếu i + 1

    • trả lại 2

  • ngược lại khi i + 2

    • ret:=3

• return (nếu ret giống với inf thì -1, ngược lại là ret)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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"));
}

Đầu vào

"abbbcde"

Đầu ra

2