LeetCode 828. 统计子串中的唯一字符（中心扩展）

示例 1：
输入: "ABC"
输出: 10
解释: 所有可能的子串为："A","B","C","AB","BC" 和 "ABC"。
     其中，每一个子串都由独特字符构成。
     所以其长度总和为：1 + 1 + 1 + 2 + 2 + 3 = 10
     
示例 2：
输入: "ABA"
输出: 8
解释: 除了 countUniqueChars("ABA") = 1 之外，其余与示例 1 相同。

示例 3：
输入：s = "LEETCODE"
输出：92
 
提示：
0 <= s.length <= 10^4
s 只包含大写英文字符

class Solution {	//C++
public:
    int uniqueLetterString(string s) {
        int i, j, k, count = 0;
        for(j = 0; j < s.size(); ++j)
        {
        	i = j-1, k = j+1;
        	while(i>=0 && s[i] != s[j])
        		i--;
        	while(k<s.size() && s[j] != s[k])
        		k++;
        	count = (count+(j-i)*(k-j))%1000000007;
        }
        return count;
    }
};

class Solution {
public:
    int uniqueLetterString(string s) {
        int count = 0;
        unordered_map<char,set<int>> m;
        for(int i = 0; i < s.size(); ++i)
        {
            m[s[i]].insert(i);
        }
        int lenl, lenr;
        for(int i = 0; i < s.size(); ++i)
        {
            auto it = m[s[i]].find(i);
            if(it == m[s[i]].begin())
                lenl = i+1;
            else
            {
                auto itl = it;
                itl--;
                lenl = i-*(itl);
            }
            if(it == --m[s[i]].end())
                lenr = s.size()-i;
            else
            {
                it++;
                lenr = *(it)-i;
            }
            count = (count+lenl*lenr)%1000000007;
        }
        return count;
    }
};

class Solution:
    def uniqueLetterString(self, s: str) -> int:
        count = 0
        for j in range(len(s)):
            i = j-1 
            k = j+1
            while i>=0 and s[i]!=s[j]:
                i -= 1
            while k<len(s) and s[j]!=s[k]:
                k += 1
            count = (count+(j-i)*(k-j))%1000000007
        return count