Count Unique Characters of All Substrings of a Given String in C++

Suppose we want to define a function called countUniqueChars(s) that will return the number of unique characters on s, so if s = "HELLOWORLD" then "H", "E", "W", "R", "D" are the unique characters since they appear only once in s, therefore countUniqueChars(s) = 5.

Now on this problem given a string s we have to find the sum of countUniqueChars(t) where t is a substring of s. (Here some substrings can be repeated so on this case we have to count the repeated ones too.)

As the answer can be very large, we can return answer modulo 10^9+7.

So, if the input is like "HELLOWORLD", then the output will be 128

To solve this, we will follow these steps −

• Define a function add(), this will take a, b,

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

• Define a function mul(), this will take a, b,

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

• From the main method, do the following −

• n := size of s

• ans := 0

• Define an array cnt of size 26

• for initialize i := 0, when i < n, update (increase i by 1), do −

  • x := s[i]

  • if size of cnt[x - 'A'] is same as 0, then −

    • insert -1 at the end of cnt[x - 'A']

  • insert i at the end of cnt[x - 'A']

• for initialize i := 0, when i < 26, update (increase i by 1), do −

  • if size of cnt[i] is same as 0, then −

    • Ignore following part, skip to the next iteration

  • insert n at the end of cnt[i]

  • for initialize j := 1, when j < size of cnt[i], update (increase j by 1), do −

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

    • ans := add(ans, temp)

• return ans

Let us see the following implementation to get better understanding −

Example

 Live Demo

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

Input

"HELLOWORLD"

Output

128