[Java/C++/Python] One pass O(N)
Foreword\nQuite similar to the question in 2262. Total Appeal of A String, \nwhich I think slightly simpler than this question.\nI also suggest you practicing t
# **Foreword**\nQuite similar to the question in [2262. Total Appeal of A String](https://leetcode.com/problems/total-appeal-of-a-string/discuss/1996390/), \nwhich I think slightly simpler than this question.\nI also suggest you practicing that first.\nI have the similar intuition and approach for both questions.\n<br>\n\n# **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:\n1. insert `"("` somewhere between the first and second `A`\n2. insert `")"` somewhere between the second and third `A`\n\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\n\n**Instead 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<br>\n\n# **Explanation**\n1. `index[26][2]` record last two occurrence index for every upper characters.\n2. Initialise all values in `index` to `-1`.\n3. Loop on string S, for every character `c`, update its last two occurrence index to `index[c]`.\n4. Count when loop. For example, if "A" appears twice at index 3, 6, 9 seperately, we need to count:\n    * For the first "A": (6-3) * (3-(-1))"\n    * For the second "A": (9-6) * (6-3)"\n    * For the third "A": (N-9) * (9-6)"\n<br>\n\n# **Complexity**\nOne pass, time complexity `O(N)`.\nSpace complexity `O(1)`.\n<br>\n\n**C++:**\n```cpp\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**Java:**\n```java\n    public int uniqueLetterString(String S) {\n        int[][] index = new int[26][2];\n        for (int i = 0; i < 26; ++i) Arrays.fill(index[i], -1);\n        int res = 0, N = S.length(), mod = (int)Math.pow(10, 9) + 7;\n        for (int i = 0; i < N; ++i) {\n            int c = S.charAt(i) - \'A\';\n            res = (res + (i - index[c][1]) * (index[c][1] - index[c][0]) % mod) % mod;\n            index[c] = new int[] {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**Python:**\n```py\n    def uniqueLetterString(self, S):\n        index = {c: [-1, -1] for c in ascii_uppercase}\n        res = 0\n        for i, c in enumerate(S):\n            k, j = index[c]\n            res += (i - j) * (j - k)\n            index[c] = [j, i]\n        for c in index:\n            k, j = index[c]\n            res += (len(S) - j) * (j - k)\n        return res % (10**9 + 7)\n```\n\n
['C', 'Python', 'Java']