Java || O(n) time || Easy Explanation
Well, let\'s do it in the most naive way by creating every substring. \n\nThis is how "LEETCODE" will look : \n\n\n\nBut it will take O(n^2) time! Pretty bad. R
Well, let\'s do it in the most naive way by creating every substring. \n\nThis is how "LEETCODE" will look : \n\n![image](https://assets.leetcode.com/users/images/b68b9780-b7ff-4006-9c18-fea85fa1bcd4_1627822711.8877163.png)\n\nBut it will take O(n^2) time! Pretty bad. Right? So, let\'s find a way to add one more character to our original string "LEETCODE". If we can do that in O(1) then it means we can solve the question in O(n) as each new character require only constant time and  we have to add \'n\' characters only.\n\n**CASE-1 (The new character is unique, suppose \'A\')**\n\nThe new column will look like :\n\n![image](https://assets.leetcode.com/users/images/5a9441a1-7d60-4dad-b7a0-e95acb524c5e_1627823298.205291.png)\n\n\'A\' gets added 9 times to the previous column\'s count because it is a unique character and will always contribute in all the previous column\'s substrings. The no. of unique characters in all substrings ending at \'A\' will be 28 + 9 = 37.\n\nThus, whenever a unique characters occurs, we just need to add (1 + number of previous characters) in the sum of previous column. Hence it can be achieved in O(1).\n\n**CASE-2 (The new character is not unique, suppose \'C\')**\n\nThe new column will look like :\n\n![image](https://assets.leetcode.com/users/images/4fa8753a-e737-40b1-b2b0-53065b2ca81f_1627823673.9783072.png)\n\n\'C\' gets added to only 4 times because it appears uniquely only till it\'s previous occurence. Once it encounters it previous occurence, it\'s impact will not be visible as we need to only count unique characters. So, the answer should be 28 + 4 = 32. But hey, it is wrong!! Why? Because this newly added \'C\' will also nullify the contributions of it\'s previous occurence which is 5. Thus the answer will be 32 - 5 = 27.\n\nThus, whenever a non-unique character occurs, we need to add (1 + number of previous characters - last occuring position of current character) to the sum of previous column and then subtract the contribution of last occurence of current character. The last occuring position of current character can be computed in O(1) . The contribution of last occurence of current character can also be computed in O(1) if we always keep a track of contributions of our characters. Hence, this entire step can be done in O(1).\n\nI know it is quite difficult to understand. Try to visualize it on your and if you still have any problem, I\'ll try my best to help you.\n\n```\nclass Solution {\n    public int uniqueLetterString(String S) {\n        int res = 0;\n        if (S == null || S.length() == 0)\n            return res;    \n        int[] showLastPosition = new int[128];\n        int[] contribution = new int[128];\n        int cur = 0;\n        for (int i = 0; i < S.length(); i++) {\n            char x = S.charAt(i);\n            cur -= contribution[x]; // removing contribution of last occurence of ith char\n            contribution[x] = (i - (showLastPosition[x] - 1)); // reset the contribution of ith char\n            cur += contribution[x]; // add the contribution of ith char\n            showLastPosition[x] = i + 1; // update the last occurence of ith char\n            res += cur;\n        }   \n        return res;\n    }\n}\n\n```\n\n
[]