Đếm các ký tự duy nhất của tất cả các chuỗi con của một chuỗi cho trước trong C ++

Giả sử chúng ta muốn xác định một hàm có tên countUniqueChars (s) sẽ trả về số ký tự duy nhất trên s, vì vậy nếu s ="HELLOWORLD" thì "H", "E", "W", "R", "D" là các ký tự duy nhất vì chúng chỉ xuất hiện một lần trong s, do đó countUniqueChars (s) =5.

Bây giờ trong bài toán này với một chuỗi s, chúng ta phải tìm tổng của countUniqueChars (t) trong đó t là một chuỗi con của s. (Ở đây một số chuỗi con có thể được lặp lại vì vậy trong trường hợp này, chúng tôi cũng phải đếm những chuỗi con được lặp lại.)

Vì câu trả lời có thể rất lớn, chúng tôi có thể trả về câu trả lời modulo 10 ^ 9 + 7.

Vì vậy, nếu đầu vào là "HELLOWORLD", thì đầu ra sẽ là 128

Để 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 add (), điều này sẽ lấy a, b,

• return (a mod m) + (b mod m)

• Xác định một hàm mul (), điều này sẽ nhận a, b,

• return (a mod m) * (b mod m)

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

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

• ans:=0

• Xác định cnt mảng có kích thước 26

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

  • x:=s [i]

  • nếu kích thước của cnt [x - 'A'] bằng 0, thì -

    • chèn -1 vào cuối cnt [x - 'A']

  • chèn i vào cuối cnt [x - 'A']

• để khởi tạo i:=0, khi tôi <26, hãy cập nhật (tăng i lên 1), thực hiện -

  • nếu kích thước của cnt [i] bằng 0, thì -

    • Bỏ qua phần sau, chuyển sang phần tiếp theo

  • chèn n vào cuối cnt [i]

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

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

    • ans:=add (ans, temp)

• trả lại ans

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

Đầu vào

"HELLOWORLD"

Đầu ra

128