Wonder full Explanation and C++ Code | Credit @LEE215
Intuition\nLet\'s think about how a character can be found as a unique character.\n\nThink about string "XAXAXXAX" and focus on making the second "A" a unique c
**Intuition**\nLet\'s think about how a character can be found as a unique character.\n\nThink about string "XAXAXXAX" and focus on making the second "A" a unique character.\nWe can take "XA(XAXX)AX" and between "()" is our substring.\nWe can see here, to make the second "A" counted as a uniq character, we need to:\n\n1. insert "(" somewhere between the first and second A\n2. insert ")" somewhere between the second and third A\nFor step 1 we have "A(XA" and "AX(A", 2 possibility.\nFor step 2 we have "A)XXA", "AX)XA" and "AXX)A", 3 possibilities.\n\nSo there are in total 2 * 3 = 6 ways to make the second A a unique character in a substring.\nIn other words, there are only 6 substring, in which this A contribute 1 point as unique string.\n\nInstead of counting all unique characters and struggling with all possible substrings,\nwe can count for every char in S, how many ways to be found as a unique char.\nWe count and sum, and it will be out answer.\n\n\n*Explanation*\n**index[26][2]** record last two occurrence index for every upper characters.\nInitialise all values in index to -1.\nLoop on string S, for every character c, update its last two occurrence index to index[c].\nCount when loop. For example, if "A" appears twice at index 3, 6, 9 seperately, we need to count:\nFor the first "A": (6-3) * (3-(-1))"\nFor the second "A": (9-6) * (6-3)"\nFor the third "A": (N-9) * (9-6)"\n\n**Complexity**\nOne pass, time complexity **O(N)**.\nSpace complexity **O(1)**.\n\n```\n\nclass Solution {\npublic:\n       int uniqueLetterString(string S) {\n        int index[26][2], res = 0, N = S.length(), mod = pow(10, 9) + 7;\n        memset(index, -1, sizeof(int) * 52);\n        for (int i = 0; i < N; ++i) {\n            int c = S[i] - \'A\';\n            res = (res + (i - index[c][1]) * (index[c][1] - index[c][0]) % mod) % mod;\n            index[c][0] = index[c][1];\n            index[c][1] = i;\n        }\n        for (int c = 0; c < 26; ++c)\n            res = (res + (N - index[c][1]) * (index[c][1] - index[c][0]) % mod) % mod;\n        return res;\n    }\n};\n\n\n\n\n```
[]