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]; } };