We all know what's the best solution, difference whose explanation wins
The most important part is how to convert this problem to another problem with easier resolution. \nBecause if we focus on the problem itself, we can only think
The most important part is **how to convert this problem to another problem with easier resolution**. \nBecause if we focus on the problem itself, we can only think about 2 approaches to solve it:\n1. Brute force, O(n^3)\n2. Brute force with memoization, O(n^2)\n\nBoth will cause LTE sadly...You can check the solution in my another post, **[Click Here](https://leetcode.com/problems/count-unique-characters-of-all-substrings-of-a-given-string/discuss/1546517/Providing-Brute-Force-O(n3)-and-O(n2)-solution-Seeking-for-weak-hire-:)**\n\nIf we convert to another problem, we can achieve O(n) time. The problem is that when you meet this problem during interview, conversion is the most important part, but intervier wants you to solve it in code in limited time. I am thinking how interviewer can lead you to the converted problem with hint...? I think it has to be a **big hint, like very big hint... :)** \n\n---\n**Conversion**\nCount Unique Characters of All Substrings of a Given String = For each character, how many substrings it can contribute to(contribute means current character is a uniq in the substring)?\n\n**Why this conversion?** \nLook at post: https://leetcode.com/problems/count-unique-characters-of-all-substrings-of-a-given-string/discuss/128952/C++JavaPython-One-pass-O(N)\n**It is very hard to think about this, if you can get through this, you convert this problem to an easily-medium problem.** \n\nMy explanation below is based on the converted idea.\n\n---\n**Expand Around Center**\nWith understanding this conversion,  we can think about it using **Expand Around Center** logic \nAssuming character \'A\' occurs at index: `i`, `j` and `k`, middle one `j` is the one we are looking at\n```\ni                   j                    k\nA                   A                    A\n```\n\n3 cases we are analyzing:\n1. How many substring **ending** at index `j` has uniq `A`, denoted as **`left`** ? \nAnswer is `j - i`, e.g. \n\t```\n\t0    1     2     3     4    5     6\n\tA    D     E     F     F    G     A   ...                   A\n\t                                  A - 1\n\t\t\t\t\t\t\t    G     A - 2\n\t\t\t\t\t\t   F    G     A - 3\n\t\t\t\t\t F     F    G     A - 4\n\t\t\t   E     F     F    G     A - 5\n\t     D     E     F     F    G     A - 6\n\t```\n2. How many substring **starting** at index `j` has uniq `A`, denoted as **`right`**?\nAnswer is `k - j`, same as above, just go to the other direction\n3. How many substring **has A in the middle** has uniq `A`, denoted as **`middle`**?\nAnswer is `(j - i - 1) * (k - j - 1)` from Math\n\nNote: `left` and `right` has **overlapping**, which is `s[j]` itself, we need to remove this in our formula with `-1`, so the final result is: `res = left + right - 1 + middle`\n\n---\n**Post-Processing**\n**Note: We need to do post-processing, because the last occured index is not considering in our loop**\n\n---\n**Medium Code**\n\n```java\nclass Solution {\n    public int uniqueLetterString(String s) {\n        int res = 0;\n        \n        int[][] occurences = new int[26][2];\n        for(int[] occurence : occurences){\n            Arrays.fill(occurence, -1);\n        }\n        \n        for(int i = 0; i < s.length(); i++){\n            int index = s.charAt(i) - \'A\';\n            // update result: how many substring has uniq characters s[i] at index occurences[index][i]?\n            // occurences[i][0], occurences[i][1], i\n\t\t\t//        left             j           i\n\t\t\t\n            int left = occurences[index][1] - occurences[index][0]; // ending at s[j]\n            int right = i - occurences[index][1]; // starting from s[j]\n            int middle= (i - occurences[index][1] - 1) * (occurences[index][1] - occurences[index][0] - 1); // s[j] in the middle\n\t\t\tres += left + middle + right - 1;\n\t\t\t\n\t\t\t// update last 2 occuences\n\t\t\toccurences[index][0] = occurences[index][1];\n            occurences[index][1] = i;\n        }\n        \n        // post-processing\n        // calculate how many substring contains uniq character which occurs at the last position\n        // because we expand around center, the last cha occurs at last position is not taken into account\n        // occurence[i][0], occurence[i][1], N\n        for(int[] occurence : occurences){\n\t\t\tint left = occurence[1] - occurence[0]; // ending at s[j]\n            int right = s.length() - occurence[1]; // starting from s[j]\n            int middle= (s.length() - occurence[1] - 1) * (occurence[1] - occurence[0] - 1); // s[j] in the middle\n\t\t\tres += left + middle + right - 1;\n        }\n        \n        return res;  \n    }\n}\n```\n\n---\nOf cource, it is easily to find out that ending at case, and starting at case, can be combined into middle case. The code is following:\n**Final Code**\n```java\nclass Solution {\n    public int uniqueLetterString(String s) {\n        int res = 0;\n        \n        int[][] occurences = new int[26][2];\n        for(int[] occurence : occurences){\n            Arrays.fill(occurence, -1);\n        }\n        \n        for(int i = 0; i < s.length(); i++){\n            int index = s.charAt(i) - \'A\';\n            // update result\n            // occurences[i][0], occurences[i][1], i\n            res += (i - occurences[index][1]) * (occurences[index][1] - occurences[index][0]);\n            occurences[index][0] = occurences[index][1];\n            occurences[index][1] = i;\n        }\n        \n        for(int[] occurence : occurences){\n            res += (s.length() - occurence[1]) * (occurence[1] - occurence[0]);\n        }\n        \n        return res;\n    }\n}\n```\n```
[]