Solution with crystal clear explanation C++. One pass O(N) and O(1) space.
This is how I thought about this problem. First, I tried to solve it with sliding window as Lee taught us :)\nThen, at some point I couldn\'t and looked in disc
This is how I thought about this problem. First, I tried to solve it with sliding window as Lee taught us :)\nThen, at some point I couldn\'t and looked in discussions and saw that it is DP. I decided to leave it for a bit and now I am back with a solution.\nI thought what can we do recursively with this:\nWell, I can solve the problem for all substrings starting at i  and then pass the solution to i + 1. But it was hard to reason what to do about the count of all the chars. \nSo, I thought what makes this problem hard? It is the duplicates.\nI solved the problem first assuming that there are no duplicate chars.\nThat\'s isn\'t hard. Use an array to store results--dp vector in my solution. dp[0] signifies score for empty string. dp[1] signifies score for strings ending at zero index and etc.\nGo from left to right. How do I calculate dp[i+1]?\nAt each index i, you know that dp[i] is the score for all substrings ending at i - 1. Well, each of those substrings you can prolong by one, using current char and for each substring you will get an extra point. Cool! The # of substrings ending at i - 1 is i. This is how many extra points you will earn. Also, let\'s not forget that s[i] by itself is also a substring with score 1.\nGo ahead and implement this piece. You will see that this code works for every string with no duplicates. \nNow, we have our first recurrence relation if we don\'t have any dups:\ndp[i + 1] = dp[i] + i + 1\n\nNow, with dups life gets harder. \nLet\'s say you see an A and this is the second one you are seeing.\nSo, I quickly realized that I need to know where my last A is. Why?\nWell, let\'s look at an example\nXXXAXXBA where X is some distinct characters.\nHere is the problem:\nWhen we calculated dp for B, we calculated it as if there are no dups, and that\'s true.\nBut let\'s say we are calculating for the second A and use the formula above. \nIt is a disaster because we have just counted A\'s as distinct chars for strings XXXAXXBA, XXAXXBA, XAXXBA, and AXXBA. So, instead of counting A\'s as 0 addition to the score, we counted them as 2 for each string.\nSo, I figured that we shouldn\'t apply the formula above directly but let\'s think about this for a second.\ndp[i] is the result for previous ending string. Let\'s find the size of the gap between cur A and previous one. In this case, the size of the gap is 3 and we add 1 for this A by itself. So, we have 4 good strings. Each one of them gets +1 for using this A, and it is unique, so we need to add +1.\nLet\'s start making changes to our formula.\n  dp[i + 1] = dp[i] + no_dup_len - (last_seen_index[char])\nThis is what we have so far.\nBut let\'s not forget about the substrings that I showed above. dp[i] counted A in every substring as +1. Now, it is no longer true. Because we are using this A, those strings shouldn\'t get anything. So, guess what? we need to subtract the number of bad strings which is last_seen_index[\'A\'] + 1\n\nThis is what I did only to discover that I made a mistake.\nIf you type this solution, it will work but only if the number of duplicates of each letter is no more than 2.\n\nWhat\'s wrong?\nLet\'s think about this scenario:\nXXAXXAXXA where X are distinct characters.\nFor first two A\'s we perform correct calculations. \nWhat happens at the third one? \nWe are going to add 3 points for XXA, XA, and A which is correct.\nBut then we are saying we are going to deduct the points for **A**XXA, **XA**XXA, ..., **XXAXXA**XXA\nHere is the problem: Remember that dp for the second A has correct results and we already substracted the points that aren\'t deserved. I explained how above.\nNow, you don\'t want to substract 2 or more times. So, what is really overcounted here?\nXXA**XXA**XXA\nThis piece is overcounted. Why? Well, because when 2-nd A was calculating its results, it calculated them for that piece as if it is the only one.\nSo, now you need to substract that piece. To find the number of strings that start somewhere and end at our 3-rd A making the total count of 2, you need to store last 2 occurences of any letter. (last_index[index][1] - last_index[index][0]) this is how you do it.\nEventually, you arrive at this dp[i + 1] = dp[i] + no_dup_len - (last_index[index][1] - last_index[index][0]) for the case when you have seen a letter.\n\nNow, in my solution dp isn\'t even needed as a result. You only need to know previous result. But I decided not to delete it so that you can see how I arrived here.\n```\n    int uniqueLetterString(string s) {\n        vector<int> dp(s.size() + 1, 0);\n        vector<vector<int>> last_index(26, {-1, -1});\n        int sum = 0;\n        for(int i = 0; i < s.size(); i++){\n            int index = s[i] - \'A\';\n            // new char.\n            if(last_index[index][1] == -1){\n                dp[i + 1] = dp[i] + i + 1;\n                last_index[index][1] = i;\n            }\n            // we have a duplicate.\n            else{\n                int last_oc = last_index[index][1];\n                int no_dup_len = i - last_oc;\n                dp[i + 1] = dp[i] + no_dup_len - (last_index[index][1] - last_index[index][0]);\n                \n                last_index[index][0] = last_index[index][1];\n                last_index[index][1] = i;\n            }\n            sum += dp[i + 1];\n        }\n        return sum;\n    }\n```
[]