C++에서 주어진 문자열의 모든 부분 문자열의 고유 문자 수 세기

countUniqueChars(s)라는 함수를 정의하여 s의 고유한 문자 수를 반환한다고 가정해 보겠습니다. 따라서 s ="HELLOWORLD"이면 "H", "E", "W", "R", "D"는 s에서 한 번만 나타나기 때문에 고유한 문자이므로 countUniqueChars(s) =5입니다.

이제 문자열 s가 주어진 이 문제에서 countUniqueChars(t)의 합을 찾아야 합니다. 여기서 t는 s의 하위 문자열입니다. (여기서 일부 하위 문자열은 반복될 수 있으므로 이 경우 반복되는 문자열도 계산해야 합니다.)

응답이 매우 클 수 있으므로 응답 모듈로 10^9+7을 반환할 수 있습니다.

따라서 입력이 "HELLOWORLD"와 같으면 출력은 128

이 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

add() 함수를 정의하면, b,
반환 (a mod m) + (b mod m)
mul() 함수를 정의하면, b,
return (a mod m) * (b mod m)
기본 방법에서 다음을 수행하십시오 -
n :=s
의 크기
답변 :=0
크기가 26인 배열 cnt 정의
initialize i :=0의 경우, i
- x :=s[i]
- cnt[x - 'A']의 크기가 0과 같으면 -
  - cnt[x - 'A']
    끝에 -1 삽입
- cnt[x - 'A']
  끝에 i 삽입
initialize i :=0의 경우 i <26일 때 업데이트(i 1만큼 증가), -
- cnt[i]의 크기가 0과 같으면 -
  - 다음 부분은 무시하고 다음 반복으로 건너뜁니다.
- cnt[i]
  끝에 n 삽입
- j 초기화의 경우:=1, j
  - 임시 :=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"