[Leetcode] 2145. Count the Hidden Sequences

2262. Total Appeal of A String

The appeal of a string is the number of distinct characters found in the string.

For example, the appeal of "abbca" is 3 because it has 3 distinct characters: 'a', 'b', and 'c'.

Given a string s, return the total appeal of all of its substrings.

A substring is a contiguous sequence of characters within a string.

Constraints:

1 <= s.length <= 10^5

s consists of lowercase English letters.

Analysis:

This question is quite straightforward if we do not care about the time complexity.

The upper bound is O(n^2), where n is the total number of chars in the string, since we only have O(n^2) substrings in total. (If we count the number of unique chars while expanding, the time complexity is O(n^2); if count after the expanding, the time complexity is O(n^3)).

But O(n^2) is not the optimal solution, which cannot pass the OJ since n could be 10^5.

One way to think about this question is that: when we add a new char [C] into account and the index of the new char is idx, then we will have (idx + 1) new substrings ending with C.

For all the (id+1) substrings, we have calculated (or known) the total unique chars before the last char, or the new char C.

Since we only care about the unique chars, we just need to know when the char C appears last time, or we just need to know the index of the previous char C, prev_idx. Before this position, the new char is not considered as a unique one. After this position, the new char will contribute 1 to the count. For all the (idx + 1) new substrings ending with the new char C, the total delta to total count is (idx - prev_idx) due to the new char C, or

delta = idx - prev_idx

If we have memorize the total count of the unique chars for the (id+1) new substrings excluding the new char C as prev_count, then we can update this to (prev_count + delta), or

cur_count = prev + delta

This is the total increase in count by taking the new char C into account.

So we just need to sum up all of these for each char in the string.

A tiny trick can be used with a vector of size ~ 26 to record the previous index of each char.

The time complexity is O(n), and space complexity is O(26), where n is the number of elements.

See the code below:

class Solution {
public:
    long long appealSum(string s) {
        long long res = 0, n = s.size(), prev_count = 0;
        vector<long long> cts(26, -1);
        for(int i=0; i<n; ++i) {
            int id = s[i] - 'a';
            int delta = i - cts[id];
            int cur_count = prev_count + delta;
            res += cur_count;
            // update
            prev_count = cur_count;
            cts[id] = i;
        }
        return res;
    }
};