Single pass O(n) time and O(1) space solution with detailed explanation
It is trivial to solve this question with brute force;\n- generate all the substrings\n- for each substring count the number of unique characters\n- keep accumu
It is trivial to solve this question with brute force;\n- generate all the substrings\n- for each substring count the number of unique characters\n- keep accumulating the result in a counter\n\nThe complexity of brute force will be `O(n^3)`; there are `n^2` substrings and getting count of each takes `O(n)` time. The fact that this question is being asked tells us that brute force is not good enough! So, let\'s try to find a better one\n\nTaking an example; `eacdaba`\n\nSome substrings are `[\'eacd\', \'eacda\', \'eacdab\', \'eacdaba\']`. The brute force solution will be counting the number of unique characters across all the substrings. Do we need to? The substrings illustrated above share common prefix(es). By calculating the count of unique characters for all the substrings we are doing wasterful computations.\n\n| `i` | `s[i]` | substrings added at this step |\n|---|----| ---- |\n| 0 | `e` | `[\'e\']` |\n| 1 | `a` | `[\'ea\', \'a\']` |\n| 2 | `c` | `[\'eac\', \'ac\', \'c\']` |\n| 3 | `d` | `[\'eacd\', \'acd\', \'cd\', \'d\']` |\n| 4 | `a` | `[\'eacda\', \'acda\', \'cda\', \'da\', \'a\']` |\n| 5 | `b` | `[\'eacdab\', \'acdab\', \'cdab\', \'dab\', \'ab\', \'b\']` |\n| 6 | `a` | `[\'eacdaba\', \'acdaba\', \'cdaba\', \'daba\', \'aba\', \'ba\', \'a\']` |\n\n**Observation** As we scan the string from left to right, at each **step `i` (0 indexed), there will be `i + 1` new substrings ending at `s[i]`**. Out of these\n\n1. **`i` substrings are formed by appending `s[i]` to the substrings from the previous step**, and\n2. **One single character substring is formed by `s[i]`**\n\nFew interesting cases arise for the `i` substrings that are formed by appending `s[i]` to the substrings from the previous step. We can classify them into the following categories\n\n1. Do not contain `s[i]`. For each of them, the count of unique characters will increase by `1`. e.g., In `step(i=1)`, substrings `[\'ea\', \'a\']` have `2` and `1` unique characters respectively. In `step(i=2)`, the count for strings `[\'eac\', \'ac\']` is `3` and `2` (`\'c\'` is not present in `s[:2]`). Let\'s say there are `Q` such substrings.\n2. Contain `s[i]` exactly once. For them the count of unqiue characters will decrease by `1`. e.g., in `step(i=3)`, `\'eacd\'` has 4 unique characters, and in `step(i=4)`, `\'eacda\'` (formed by appending `\'a\'` to `\'eacd\'`) has 3 unique characters. Let\'s say there are `R` such substrings.\n3. Contain `s[i]` more than once. The count of unique characters stays the same for such substrings. e.g., in `step(i=5)`, `\'acdab\'` has 3 unique characters, and in `step(i=6)`, `\'acdaba\'` (formed by appending `\'a\'` to the \'acdab\'`) still has 3 unique characters. As the count of unique characters doesn\'t change for these substrings, we do not need to worry about them.\n\nSo, we arrive at - if the count of unique characters of substrings from the previous steps is `P`, then the count of unique characters for the current step will be `P + Q - R + 1`. The trailing `1` is for the single character substring formed by `s[i]`.\n\nNow the problem is reduced to finding\n\n1. `Q`; num of suffixes of the slice `s[:i]` which do not contain `s[i]`, and\n2. `R`; num of suffixes of the slice `s[:i]` which contain `s[i]` exactly once\n\nNote that if `s[i]` is not present in the slice `s[:i]`, then `Q=i` and `R=0`.\n\nTo find `Q` and `R` more generally, let\'s consider `step(i=4)` from the above example. `[\'eacd\', \'acd\', \'cd\', \'d\']` are the subtrings from `step(i=3)`. In `step(i=4)`, we will append `\'a\'` to these substrings to get new ones. To find `Q` we need to find number of substrings from `step(i=3)` which do not contain `\'a\'`. There are `2` (`\'cd\'` and `\'d\'`) such substrings. So, `Q=2`. If we think about it this is nothing but the number of characters between the current character (`a` at index `i=4`) and its last occurence (at `i=1`) in the string.\n\nMore generally speaking, if the current character (i.e., `s[i]`) was last seen at index `j` in the string, we can represent the string `s` as\n\n```\ns_0,s_1,s_2,...,s_j,s_j+1,...,s_i-1,s_i,...\n```\n\nAll the suffixes of the slice `s[j+1:i]` (or the substring `s_j+1,...,s_i-1`) will not contain `s[i]`. There will be `(i-1) - (j+1) + 1` or `i-1-j` such suffixes. So, we have\n\n`Q = i-1-j`, where `j` is the index of the last occurrence of `s[i]`.\n\nExtending the logic, `R`, i.e., number of substrings from the previous step which have the current character (`s[i]`) exactly once is nothing but the number of characters between the last and the second last occurence of `s[i]` in the string. If `k` is the index of the second last occurrence of `s[i]`, then we can represent `s` as\n\n```\ns_0,s_1,s_2,...,s_k,s_k+1,...,s_j,s_j+1,...,s_i-1,s_i,...\n```\n\nThe suffixes of the slice `s[k+1:j+1]` will contain `s[i]` exactly once. There are `j - (k+1) + 1` or `j-k` such suffixes. So, we have\n\n`R = j-k`, where `k` is the index of the second last occurrence of `s[i]`.\n\nThis completes our algorithm - while scanning the string from left to right, at step `i` (`0 <= i < len(s)`)\n1. Find `(k, j)` which are the indices of the last two occurences of `s[i]`\n2. Count of the current step is `P + Q - R + 1`, where `P` is the count from the previous step and `Q` and `R` are defined in terms of `j` and `k` by the formulas defined above\n3. Update total count with the count from current step\n4. Count of the current step becomes `P`\n5. Update the last two occurences of `s[i]` as `(j, i)`.\n\nTime complexity = `O(n)` as we do a single scan of `s`.\nSpace complexity = `O(1)` for we are dealing with constant (`26`) number of alphabets and for each alphabet we need constant (`2`) space to keep track of its last two occurrences in `s`.\n\nHere is the python code\n\n```\nclass Solution(object):\n    def uniqueLetterString(self, s):\n        if s is None:\n            raise RuntimeError("Bad input; s cannot be None")\n        lastSeen = {}\n        retval = 0\n        lastStepCount = 0\n        for i in range(len(s)):\n            lastTwoSeenIndices = lastSeen.get(s[i], None)\n            if not lastTwoSeenIndices:\n                currentStepCount = lastStepCount + i + 1\n                lastSeen[s[i]] = (-1, i)\n            else:\n                secondLastSeenIndex, lastSeenIndex = lastTwoSeenIndices\n                numOfSuffixesWithoutCurrChar = i - 1 - lastSeenIndex\n                numOfSuffixesWithJustOneOccurrenceOfCurrChar = \\\n                    lastSeenIndex - secondLastSeenIndex\n                currentStepCount = \\\n                    lastStepCount + \\\n                    1 + \\\n                    numOfSuffixesWithoutCurrChar - \\\n                    numOfSuffixesWithJustOneOccurrenceOfCurrChar\n                lastSeen[s[i]] = (lastSeenIndex, i)\n            \n            retval += currentStepCount\n            lastStepCount = currentStepCount\n\n        return retval\n```
['Python']