[Java] Clean O(n) Solution || detailed explanation of why it works
The Key of solving this problem in linear time is find the relationship between  sum of countUniqueChars() for substrings ending index i and  sum of countUnique
The Key of solving this problem in linear time is find the relationship between  **sum of countUniqueChars() for substrings ending index i** and  **sum of countUniqueChars() for substrings ending index i-1**.  This article aims to leave leave no room for ambiguity\u200B of how this algorithm works. \n\nFor each index i, consider all substrings ending at index i: \n```\ns[0 : i] , ... , s[i-1 : i]  , s[i : i];\n```\nComparing with all substrings ending at index i-1: \n```\ns[0: i-1], ... , s[i-1, i-1]\n```\n\nWe know the result for s[i : i] which only contains 1 character: \n```\ncountUniqueChars(s[i: i]) = 1\n```\n\nThen we want to find the relationship between: \n```\ncountUniqueChars(s[0: i])    v.s.  countUniqueChars(s[0: i-1])\ncountUniqueChars(s[1: i])    v.s.  countUniqueChars(s[1: i-1])\n\t\t  ...                               ... \ncountUniqueChars(s[i-1: i])  v.s.  countUniqueChars(s[i-1: i-1])\n```\n\nDenote c = s.charAt(i), then for all substrings ending at index i-1, there could be 3 cases: \n```\n// denote char c = s.charAt(i);\nCase 1. s[k : i-1] contains 0 c              ==> countUniqueChars(s[k : i]) = countUniqueChars(s[k : i-1]) + 1\nCase 2. s[k : i-1] contains 1 c              ==> countUniqueChars(s[k : i]) = countUniqueChars(s[k : i-1]) - 1\nCase 3. s[k : i-1] contains at least 2 c     ==> countUniqueChars(s[k : i]) = countUniqueChars(s[k : i-1])\n```\nThe reasoning is pretty starightforward: \n```\n Case 1.  s[k : i] has one more unique char (c itself) comparing to s[k : i-1]\n Case 2.  s[k : i] has one less unique char (c itself) comparing to s[k : i-1]\n Case 3.  any unique char in s[k : i-1] is still unique in s[k : i]; \n          c itself is not an unique char for either s[k : i-1] or s[k : i]\n```\n\nThus we find the relation between the **sum of countUniqueChars() for substrings ending index i** and  **sum of countUniqueChars() for substrings ending index i-1**.  \n\n```\n        sum of countUniqueChars() for index i \n     =  sum of countUniqueChars() for index i-1  +  #(case 1)  -  #(case 2)  +  1  \n```\nwhere the last 1 stands for the substring s[i : i]. The remaining things are just calculating the number of substrings in Case 1 & Case 2. We denote: \n\n```\n// p : index of last appearance of c;     or -1 if not exist (c never appears)\n// q : index of second last appearance of c;    or -1 if not exist (c never appears twice)\n```\n\nThen for s[k : i-1] whose starting point is k: \n```\nCase 1. k in [p+1, i-1]   <==>  c appears 0 time in s[k : i-1]  \nCase 2. k in [q+1, p]     <==>  c appears 1 time in s[k : i-1]  \nCase 3. k in [0, q]       <==>  c appears at least 2 times in s[k : i-1]  \n```\n\nThus we have: \n```\n#(Case 1)  =  (i-1) - (p+1) + 1 \n           =  i - p - 1\n#(Case 2)  =  p - (q+1) + 1  \n           =  p - q\n```\nwhich leads to \n\n```\n    sum of countUniqueChars() for index i \n =  sum of countUniqueChars() for index i-1  +  (i - p - 1)  -  (p - q)  +  1  \n =  sum of countUniqueChars() for index i-1  +  (i - p - p + q)\n```\nNotice we set the default value of p & q to -1 to handles the cases with invalid intervals. Now we finish the reasoning. Getting the solution is very straightforward. \n\n```\nclass Solution {\n    public int uniqueLetterString(String s) {\n        \n\t\tint[] lastSeen = new int[26];\n        Arrays.fill(lastSeen, -1);\n        \n        int[] secLastSeen = new int[26];\n        Arrays.fill(secLastSeen, -1);\n\t\t\n\t\tint count = 0, res = 0;\n\t\n\t\tfor (int i = 0; i < s.length(); i++) {\n            int idx = s.charAt(i) - \'A\';\n            int p = lastSeen[idx];\n            int q = secLastSeen[idx];\n\t\t\t\n            count += i - p - p + q;\n            res += count;\n            \n            secLastSeen[idx] = lastSeen[idx];\n            lastSeen[idx] = i;\n\t\t}\n        \n\t\treturn res;\n    }\n}\n```
['Java']