สตริงย่อยส่วนใหญ่ที่สั้นที่สุดใน C ++

สมมติว่าเรามีสตริงตัวอักษรตัวพิมพ์เล็ก s เราต้องหาความยาวของสตริงย่อยที่สั้นที่สุด (ความยาวขั้นต่ำคือ 2) เพื่อให้ตัวอักษรบางตัวปรากฏมากกว่าตัวอักษรอื่นๆ รวมกัน หากเราหาวิธีแก้ปัญหาไม่ได้ ให้คืนค่า -1

ดังนั้น หากอินพุตเป็นเหมือน "abbcde" ผลลัพธ์จะเป็น 2 สตริงย่อย "bb" จะมีความยาวขั้นต่ำและจะปรากฏมากกว่าตัวอักษรอื่นๆ

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดฟังก์ชัน ok() ซึ่งจะใช้อาร์เรย์ cnt

• รวม :=0, maxVal :=0

• สำหรับแต่ละองค์ประกอบใน cnt ทำ

  • รวม :=รวม + มัน

  • maxVal :=สูงสุดของ maxVal และมัน

• คืนค่า จริง เมื่อ maxVal> (ผลรวม - maxVal)

• จากวิธีหลัก ให้ทำดังนี้ −

• n :=ขนาดของ s

• ret :=inf

• สำหรับการเริ่มต้น i :=0 เมื่อ i

  • ถ้า i + 1

    • กลับ 2

  • มิฉะนั้น เมื่อ i + 2

    • ย้อนหลัง :=3

• return (ถ้า 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