[C++] O(1) Space || O(n) Time || 1-Pass || In-depth Explanation and Examples
Intuition\n\n- The intuition used to solve this problem is derived from a solution to problem 2916. Subarrays Distinct Element Sum of Squares II.\n- As you go t
# Intuition\n\n- The intuition used to solve this problem is derived from a solution to problem [2916. Subarrays Distinct Element Sum of Squares II](https://leetcode.com/problems/subarrays-distinct-element-sum-of-squares-ii/).\n- As you go through the string, you can keep track of the number of unique elements in all substrings ending at index `i`. This will be explained in detail later.\n\n# Example and Explanation\n\nLets use the example `LEETCODE`. We will build this string from left to right. And we will check \n\nStarting with `L`, ther is a single substring that ends with `L`: `L`. There is 1 unique character, and therefore the score is currently 1.\n\nMoving on, we have `LE`, which gives the substrings: `LE` and `E`. They have respective scores of 2 (`LE`) and 1 (`E`), for a total score of 3.\n\nHowever, when we add the next letter, `E`, something happens: `LEE` gives substrings `LEE`, `EE`, and `E`. All other substrings have already been processed previously, so we only need to worry about these ones. `LEE` has a score of 1, while `EE` has a score of 0, and `E` has a score of 1. If you don\'t see a pattern yet, look below. Each number represents the length of the substring starting at the character directly above it, ending at the end of the string above it. For example, the 1 underneath `LEE` means that the substring `LEE` has a score of 1, while the 0 underneath `EE` means `EE` has a score of 0.\n\n    L\n    1\n    \u2013\u2013\u2013\u2013\u2013\n    LE\n    21\n    \u2013\u2013\u2013\u2013\u2013\n    LEE\n    101\n\nWhen we encounter a character we have already seen before, **some** number of substrings from the previous iteration will have their score decreased by 1. More specifically, **all** the substrings which only contain the current character **ONCE** will have their score decreased by 1.\n\nWhen we encounter a character we haven\'t seen before, we can safely add [max current substring size + 1] score to the current score. For example:\n\n    A\n    1       -> 0 + 1 = 1 (add 1, total score 1)\n    \u2013\u2013\u2013\u2013\u2013\n    AB\n    21      -> 1 + 1 = 2 (add 2, total score 3)\n    \u2013\u2013\u2013\u2013\u2013\n    ABC\n    321     -> 2 + 1 = 3 (add 3, total score 6)\n\n    A, AB, ABC, BC, B, C \n    = 1, 2, 3, 2, 1, 1 \n    = 10\n    = 1 + 3 + 6 (all score)\n\nUnfortunately, to find the score we need to subtract when we come across a old character, we have to keep track of both the **last index of that character** and also the **last last index of that character**. We need to keep track of the last 2 occurrences of the character because we can add score to all substrings that start **AFTER** the previous occurrence. However, we need to subtract score from all the substrings that start **BETWEEN** the previous and previous-previous occurrence. This is because, for these strings, the previous occurrence of the character is the **ONLY** occurrence of that character. When we add another occurrence, they lose 1 from their score, as that character is no longer unique. Example: `LEAETCOE`\n\n    LE | AE | TCO | E\n\nEverything between the first `LE` and `TCO` will have its score decreased when the last `E` is concatenated to the end of the string. `AETCO` and `ETCO` both contain `E` while excluding the first `E`. Therefore, their respective `E`\'s contribute score. `AETCOE`\'s score is 1 less than `AETCO`, and `ETCOE` is 1 less than `ETCO`, because adding another `E` reduces the score by getting rid of one unique letter.\n\nHowever, `TCO`, `CO`, and `O` are all fine, and will all simply increase score after having `E` concatenated to the end of them.\n\nFrom this pattern, we can derive a formula to compute the number of  unique characters of all substrings in O(n) time. Here is the pseudocode:\n\n    for all characters in a string\n        if character has not been seen before\n            add 1 for all substrings (or index + 1) to temp variable\n            update previous[current character]\n        else if character has been seen before\n            subtract (prev index - second prev index) from temp\n            add index - prev index to temp\n            update both previous[current character] and second previous[current character]\n        add temp to total\n\n    return total\n\n# Code\n```\nclass Solution {\npublic:\n    int uniqueLetterString(string s) {\n        //declare basic vars\n        int len = size(s),\n                  prev[27],\n                  sec_prev[27],\n                  ret = 0,\n                  temp = 0;\n        //set array memoy\n        memset(prev,-1,sizeof(prev)),\n        memset(sec_prev,-1,sizeof(sec_prev));\n        //1-pass\n        for(index = 0; index < len; ++index) {\n            int nchar = s[index]-\'A\';\n            //if this character has NOT been seen before\n            if(prev[nchar] == -1)\n                prev[nchar] = index,\n                temp += index + 1;\n            //if this character HAS been seen before\n            else temp -= prev[nchar] - sec_prev[nchar],\n                temp += index - prev[nchar],\n                sec_prev[nchar] = prev[nchar],\n                prev[nchar] = index;\n            //add sum of all current substrings\' unique elements\n            //to total\n            ret += temp;\n        }\n        return ret;\n    }\n};\n```
['String', 'C++']