Leetcode - 2262 Total Appeal of A String.md

Posted on | In , ,

A very interesting dp problem.

Solution

At first, I thought I should record the position of each character into 26 arrays. When we traverse from 0 to n, we can find that the appeal of a substring starts from index i, can be divided into at most 26 parts(As we only have 26 letters). As a result, we can find what letter we haven’t met and using Binary search to find the next nearest letter that we haven’t met. The time complexity is O(nlogn). I got TLE with this solution.

Another Way to solve this problem is DP. Let’s define DP[i] as the total appeal of all substrings end at index i. Then, DP[i] is made up of two parts:

  1. We append letter[i] to all the substrings ends at index i-1. Here we suppose we don’t add a new distinct letter. We will calculate the contribution of adding new distinct letter in the second part. Here we just take letter[i] as a letter we already have at index i-1. The contribution of this part is DP[i-1].
  2. Here we consider the situation that letter[i] is a new distinct letter. In order to make it a new distinct letter, we need to find the last position that letter[i] appears, call it position j. The contribution of letter[i] as a new distinct letter is i-j;

When we add them up, then we can get the answer.

Inspiration

When handling counting problem, a state meets demands and ends at i is helpful and should be considered as a solution.

Code

TLE Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
    long long appealSum(string s) {
        int n = s.length();
        long long ans = 0;
        vector<int> pos[26];
        for(int i=0;i<n;i++) {
            pos[s[i]-'a'].push_back(i);
        }
        for(int i=0;i<26;i++) {
            pos[i].push_back(n);
        }
        for(int i=0;i<n;i++) {
            unordered_set<int> dict;
            int j = i;
            while(j<n) {
                dict.insert(s[j]-'a');
                int mins = n;
                for(int k=0;k<26;k++) {
                    if(dict.find(k)==dict.end()) {
                        int index = lower_bound(pos[k].begin(), pos[k].end(), j)-pos[k].begin();
                        mins = min(mins, pos[k][index]);
                    }
                }
                ans+=(mins-j)*dict.size();
                j = mins;
            }
        }
        return ans;
    }
};

AC Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    long long appealSum(string s) {
        long long prev[26], ans = 0, cur = 0;
        for(int i=0;i<26;i++){
            prev[i] = -1;
        }
        for(int i=0;i<s.length();i++) {
            cur += (i-prev[s[i]-'a']);
            prev[s[i]-'a'] = i;
            ans+=cur;
        }
        return ans;
    }
};