Concise DP O(n) solution
Let dp[i] is sum of unique char in all substring ending at i, then the answer is sum(dp[i]), i=[0..n-1]. It\'s not difficult to get the recursive formula:\n   d
Let `dp[i]` is sum of unique char in all substring ending at `i`, then the answer is `sum(dp[i]), i=[0..n-1]`. It\'s not difficult to get the recursive formula:\n   `dp[i] = dp[i-1] + (i - first_from_i(s[i])) - (first_from_i(s[i]) - second_from_i(s[i]))`\n\t \nTake the below example:\n```\nBBBBBBBBBBBBBBBBBOABCDOABCOABC\n                 ^    ^   ^\n                 s    f   i\n\ndp[i] = dp[i-1] + (i-f) - (f-s)\n```\nWhen extending `s[i]` to all substrings ending with `s[i-1]`, there are `(i-f)` more unique char `s[i]`, and `(f-s)` less unique char because of duplicate of `s[i]`.\n\nThe implementation is quite simple. Here is Java version:\n```\n    public int uniqueLetterString(String s) {\n            final int MOD = 1000000007;\n            int res = 0, dp = 0;\n            int[] first = new int[26], second = new int[26];\n\n            for (int i = 0; i < s.length(); i++) {\n                int ci = s.charAt(i) - \'A\';\n                dp = dp + 1 + i - first[ci] * 2 + second[ci];\n                res = (res + dp) % MOD;\n\n                second[ci] = first[ci];\n                first[ci] = i + 1;\n            }\n\n            return res;\n    }\n```\n\nPlease vote if you like :)
[]