O(N) Java Solution, DP, Clear and easy to Understand
In each loop, We caculate cur[i], which represent the sum of Uniq() for all substrings whose last char is S.charAt(i).\n\nFor example, \nS = \'ABCBD\'\nWhen i =
In each loop, We caculate `cur[i]`, which represent the sum of Uniq() for all substrings whose last char is S.charAt(i).\n\nFor example, \n`S = \'ABCBD\'`\nWhen i = 2,  `cur[2] = Uniq(\'ABC\') +  Uniq(\'BC\') +  Uniq(\'C\')`\nWhen i = 3,  `cur[3] = Uniq(\'ABCB\') +  Uniq(\'BCB\') +  Uniq(\'CB\') +  Uniq(\'B\')`\n\nNotice, we append char \'B\' into each previous substrings. Only in substrings \'CB\' and \'B\', the char \'B\' can be identified as uniq. The contribution of \'B\' from cur[2] to cur[3] is `i - showLastPosition[\'B\']`. At the same time, in substrings \'ABCB\', \'BCB\', the char \'B\' can\u2018t\u2019 be identified as uniq any more, the previous  contribution of \'B\' should be removed.\n\nSo we have`\'cur[i] = cur[i - 1] - contribution[S.charAt(i)] +  (i - showLastPosition[S.charAt(i)]) `\nThen the new `contribution[S.charAt(i)] = i - showLastPosition[S.charAt(i)]`\n\nThe final result is the sum of all `cur[i]`. \n\nThanks [@wangzi6147](https://discuss.leetcode.com/user/wangzi6147) for this picture:\n![image](https://s3-lc-upload.s3.amazonaws.com/users/ankailiang/image_1525586587.png)\n\n\n\n\nThis is my code. I didn\'t do mod operation, but it still pass : )\n```\n    public int uniqueLetterString(String S) {\n        \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]; \n            contribution[x] = (i - (showLastPosition[x] - 1));\n            cur += contribution[x]; \n            showLastPosition[x] = i + 1;\n            res += cur;\n        }   \n        return res;\n    }\n```\n\nThe showLastPosition[x] represent the last showing positon of char x befor i. (The initial showLastPosition[x] for all chars should be \'-1\'. For convenience, I shift it to \'0\'. It may cause some confusion, notice I update "showLastPosition[x] = i + 1" for each loop.)
[]