C++ Counting Solution O(N)
Runtime: 49 ms, faster than 76.04% of C++ online submissions for Count Unique Characters of All Substrings of a Given String.\nMemory Usage: 16 MB, less than 46
Runtime: 49 ms, faster than 76.04% of C++ online submissions for Count Unique Characters of All Substrings of a Given String.\nMemory Usage: 16 MB, less than 46.87% of C++ online submissions for Count Unique Characters of All Substrings of a Given String.\n\n\n```\nCounting number of unique chars in all substrings is same as the sum of substring count on which each char is a unique char.\n\nNumber of substring where char X on index K is unique => ( Length from K to previous occuerence of X) * ( Length from K to next occuerence of X)\n\nSo, we precalculate the right occuerence index for each char.\nThen loop from left to right and store the left occuerence of char on the way and count number of substring on which each char is unique.\n```\n\n\n```\nclass Solution {\npublic:\n    int uniqueLetterString(string s) {\n        \n        int sl = s.length();\n        int count = 0;\n        \n        // store last index of each char from right to left\n        vector<int>indexes(26,sl);\n        \n        // store right occuerence index of each char position\n        vector<int>rightIndexes(sl);\n        int index;\n        \n        for(int i =sl-1;i>=0;i--)\n        {\n            index  = s[i] - \'A\';\n            \n            rightIndexes[i] = indexes[index];\n            \n            // update last occurence index \n            indexes[index] = i;\n        }\n        \n        // store last occuerence of each char from left to right\n        vector<int>leftIndexes(26,-1);\n        \n        for(int i=0;i<sl;i++)\n        {\n            index = s[i] - \'A\';\n        \n            // total substring where s[i] is unique => left length * right length\n            count+= (i - leftIndexes[index]) * (rightIndexes[i]-i);\n            \n            // update last occurence index\n            leftIndexes[index] = i;\n        }\n                \n        return count;\n    }\n};\n```
['String', 'C', 'Counting']