Simple Java Solution | O(n) Time and Space
Let M be the number of subarrays that a particular character appears without repetition. Then the character constributes M to the final answers. The sum of cont
Let **M** be the number of subarrays that a particular character appears without repetition. Then the character constributes **M** to the final answers. The sum of contributions of all characters is the final answer. \n\n**Question**: How do we calculate the contribution made by each character? \nThis is is very simple and can be done in **linear time**. \n\nLet **K** be a character in a particular string. Let **left** be the number of contiguous characters to the **left** of **K** not containing any **K**. Let **right** be the number of contiguous characters to the right of **K** not containing any **K**.\n\nThe number of subarrays that **K** appears exactly onces are **(left+1)*(right+1)**. \n\nFor example, Consider the first  **O** in **SOLUTION**, there is only **1** character to the left of **O** and there are **4** characters to the right of **O** that do not include any other O. Hence, **left = 1, right = 4**. Therefore, the number of subarrays that the first **O** in **SOLUTION** appears exactly once is **(1+1)(4+1) = 10**, which correspond to the following subarrays\nO, OL, OLU, OLUT, OLUTI\nSO, SOL, SOLU, SOLUT, SOLUTI\nThis means that the contribution that the first O in **SOLUTION** makes to the final answer is **10**.\n\nMore Example: Consider LEETCODE\nL ----> left = 0, right = 7, subarrays = (0+1) * (7+1) = 8\nE ----> left = 1, right = 0, subarrays = (1+1) * (0+1) = 2\nE ----> left = 0, right = 4, subarrays = (0+1) * (4+1) = 5\nT ----> left = 3, right = 4, subarrays = (3+1) * (4+1) = 20\nC ----> left = 4, right = 3, subarrays = (4+1) * (3+1) = 20\nO ----> left = 5, right = 2, subarrays = (5+1) * (2+1) = 18\nD ----> left = 6, right = 1, subarrays = (6+1) * (1+1) = 14\nE -----> left = 4, right = 0, subarrays = (4+1) * (0+1) = 5\n\n**Total contribution for all characters = 8 + 2 + 5 + 20 + 20 + 18 + 14 + 5 = 92**\n\nIn my approach, I iterated the given string once from left to right and store the **left** count for every character. Next, I iterated the string  from right to left to get the **right** count for every character. I then multiply **left** count with **right** count for each character and add the result to the **total**.\n```\nclass Solution {\n    public int uniqueLetterString(String s) {\n        int len = s.length();\n        \n        int[] temp = new int[26];\n        \n        //for counting chars to the left of and not equal to the current character \n        int[] leftCount = new int[len];\n        Arrays.fill(temp,-1);\n        \n        \n        int index;\n        for(int i=0; i<len; i++){\n            index = s.charAt(i)-\'A\';\n            leftCount[i] = temp[index]==-1?i+1:i-temp[index];\n            temp[index] = i;\n        }\n        Arrays.fill(temp,-1);\n        int total = 0, right;\n        for(int i=len-1; i>=0; i--){\n            index = s.charAt(i)-\'A\';\n            right = temp[index]==-1?len-i:temp[index]-i;\n            total += right * leftCount[i];\n            temp[index] = i;\n        }\n        return total;\n    } \n}\n```
[]