นับอักขระที่ไม่ซ้ำของสตริงย่อยทั้งหมดของสตริงที่ระบุใน C++

สมมติว่าเราต้องการกำหนดฟังก์ชันที่เรียกว่า countUniqueChars ซึ่งจะคืนค่าจำนวนอักขระที่ไม่ซ้ำใน s ดังนั้นหาก s ="HELLOWORLD" ตามด้วย "H", "E" "W", "R", "D" เป็นอักขระเฉพาะเนื่องจากปรากฏเพียงครั้งเดียวใน s ดังนั้น countUniqueChars =5

สำหรับปัญหานี้เมื่อกำหนดสตริง s เราต้องหาผลรวมของ countUniqueChars(t) โดยที่ t เป็นสตริงย่อยของ s (ในที่นี้สตริงย่อยบางอันสามารถทำซ้ำได้ ในกรณีนี้เราต้องนับสตริงที่ซ้ำกันด้วย)

เนื่องจากคำตอบอาจมีขนาดใหญ่มาก เราสามารถส่งคืนโมดูโลคำตอบ 10^9+7

ดังนั้นหากอินพุตเป็น "HELLOWORLD" เอาต์พุตจะเป็น 128

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

• กำหนดฟังก์ชัน add() ซึ่งจะใช้เวลา a, b,

• กลับ (a mod m) + (b mod m)

• กำหนดฟังก์ชัน mul() ซึ่งจะใช้ a, b,

• กลับ (a mod m) * (b mod m)

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

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

• ตอบ :=0

• กำหนดอาร์เรย์ขนาด 26

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

  • x :=s[i]

  • ถ้าขนาดของ cnt[x - 'A'] เท่ากับ 0 แล้ว −

    • ใส่ -1 ต่อท้าย cnt[x - 'A']

  • ใส่ i ต่อท้าย cnt[x - 'A']

• สำหรับการเริ่มต้น i :=0 เมื่อ i <26 อัปเดต (เพิ่ม i ขึ้น 1) ให้ทำ -

  • ถ้าขนาดของ cnt[i] เท่ากับ 0 แล้ว −

    • ละเว้นส่วนต่อไปนี้ ข้ามไปยังการทำซ้ำถัดไป

  • ใส่ n ต่อท้าย cnt[i]

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

    • temp :=mul(cnt[i, j] - cnt[i, j - 1], cnt[i, j + 1] - cnt[i, j])

    • ans :=add(ans, temp)

• กลับมาอีกครั้ง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
const lli m = 1e9 + 7;
class Solution {
   public:
   lli add(lli a, lli b){
      return (a % m) + (b % m);
   }
   lli mul(lli a, lli b){
      return (a % m) * (b % m);
   }
   int uniqueLetterString(string s) {
      int n = s.size();
      int ans = 0;
      vector<int> cnt[26];
      for (int i = 0; i < n; i++) {
         char x = s[i];
         if (cnt[x - 'A'].size() == 0) {
            cnt[x - 'A'].push_back(-1);
         }
         cnt[x - 'A'].push_back(i);
      }
      for (int i = 0; i < 26; i++) {
         if (cnt[i].size() == 0)
         continue;
         cnt[i].push_back(n);
         for (int j = 1; j < cnt[i].size() - 1; j++) {
            lli temp = mul(cnt[i][j] - cnt[i][j - 1], cnt[i][j +
            1] - cnt[i][j]);
            ans = add(ans, temp);
         }
      }
      return ans;
   }
};
main(){
   Solution ob;
   cout << (ob.uniqueLetterString("HELLOWORLD"));
}

อินพุต

"HELLOWORLD"

ผลลัพธ์

128