An extremely simple explanation
Let us start with a simple example:\n\nConsider string s=ABC \nAll substrings of this string are A, B, C, AB, BC, ABC\n\n- What is total contribution of charact
Let us start with a simple example:\n\nConsider string `s=ABC` \nAll substrings of this string are `A, B, C, AB, BC, ABC`\n\n- What is total contribution of character `A` to all substrings?\n=> 3\n- What is total contribution of character `B` to all substrings?\n=> 4\n- What is total contribution of character `C` to all substrings?\n=> 3\n\nIf a character `c=s[i]` is **unique**, its total contribution is `(i+1)*(N-i)`\nConvice yourself that is indeed the case. \n> Alternatively, how many sub-strings will contain the character `s[i]`?\n\nNow, Consider string `s=ABA` \nAll substrings of this string are `A, B, A, AB, BC, ABA`\n\n- What is total contribution of `first` character `A` to all substrings?\n=> 3\n- What is total contribution of character `B` to all substrings?\n=> 4\n- What is total contribution of `third` character `A` to all substrings?\n=> 1\n\nIf a character `c=s[i]` is not unique, , it will contribute within a `restricted` window. For example if\n            `s = ".....c ..... c .... c ....."`        \n the middle `c` will contribute only within the window `.....c [..... c ....] c .....`\n\nNow the problem becomes easy. At every position, just ask yourself, \n- When did I last see this character?\n- When will I next see this character?\n\nIf a character `c=s[i]` is **non-unique**, its total contribution is `(i - prevSeen[i] ) * ( nextSeen[i] - i ) `\nConvice yourself that is indeed the case. \n\n```\nclass Solution {\npublic:\n    int uniqueLetterString(string s) {\n        \n        int N = s.size(), count=0;\n        \n        array<int,128> prevSeen; prevSeen.fill(-1);\n        array<int,128> nextSeen; nextSeen.fill(N);\n        \n        vector<int> prevPos(N,0), nextPos(N,0); \n        \n        for(int i=0; i<N; ++i) {\n            prevPos[i] = prevSeen[s[i]];\n            prevSeen[s[i]] = i;\n        }\n        \n        for(int i=N-1; i>=0; --i) {\n            nextPos[i] = nextSeen[s[i]];\n            nextSeen[s[i]] = i;\n        }\n        \n        for(int i=0; i<N; ++i) {\n            count += (i-prevPos[i])*(nextPos[i]-i);\n        }\n        \n        return count;\n    }\n};\n```
[]