Skip to content

Instantly share code, notes, and snippets.

@kanrourou
Created May 8, 2018 04:16
class Solution {
public:
int uniqueLetterString(string S) {
int len = S.size();
long long curr = 0, res = 0;
if(!len)return 0;
const int MOD = 1000000007;
unordered_map<char, vector<int>> idxes;
vector<int> peek(len, 0);
for(int i = 0; i < len; ++i)idxes[S[i]].push_back(i);
for(auto& p : idxes)
{
p.second.push_back(len);
curr += calculate(idxes, peek, p.first);
}
for(const auto& c : S)
{
res += curr;
long long old = calculate(idxes, peek, c);
++peek[c - 'A'];
curr += calculate(idxes, peek, c) - old;
}
return res % MOD;
}
private:
long long calculate(unordered_map<char, vector<int>>& idxes, vector<int>& peek, char c)
{
auto idx = idxes[c];
int i = peek[c - 'A'];
return i == idx.size() - 1? 0 : idx[i + 1] - idx[i];
}
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment