Java | DP 3ms | easy to understand | Time O(n) | Space O(1)
To solve problem, we can transform to solve its subproblem.\nFor instacnce, we have "ABC" as input. \nAfter the first input, the contribution is 1, and the incr
To solve problem, we can transform to solve its subproblem.\nFor instacnce, we have "ABC" as input. \nAfter the first input, the contribution is 1, and the increase number of contribution is 1. \nAfter the second input, the contribution is 3, and the increase number of contribution is 2. (from "A" -> "AB")\nAfter the second input, the contribution is 6, and the increase number of contribution is 3. (from "AB" -> "ABC");\nAnd the answer is (1) + (1+2) + (1+2+3) = 10\n\nIf we have a function f(x) for contribution, and a function g(x) for increase of contribution.\nf(x) = f(x-1) + g(x);\nAnd we can sum all the f(x) to get the final answer.\n\nWhat if we have duplications? Like "ABA"\nfrom "AB" -> "ABA", the increase number of contribution is only 2.  \nThe last A only contribute to A **B** **A**\ng(x) = current Index - previous duplication\'s index\nAnd from the description, we also know that we need to minus the previous A\'s contribution.\nFor example, "C A B A", we need to minus A\'s contribution in "**C A** B A"\nfinally, g(x) = current Index - previous duplication\'s index - previous duplicaiton\'s contribution.\n\n```\npublic int uniqueLetterString(String s) {\n        final int n = s.length();\n\t\tint[] prev = new int[26];\n\t\tint[] contribution = new int[26];\n\t\tArrays.fill(prev, -1);\n\t\tint cur = 0, res = 0;\n\t\tint mod = 1000000007;\n\n\t\tfor (int i = 0; i < n; i++) {\n\t\t\tint idx = s.charAt(i) - \'A\';\n\t\t\tcur -= contribution[idx]; // if exist duplication, minus the previous contribution\n\t\t\tcontribution[idx] = i - prev[idx]; // calculate increase g(x)\n\t\t\tcur += contribution[idx]; // current contribution f(x) = f(x-1) + g(x);\n\t\t\tres += cur % mod;\n\t\t\tprev[idx] = i;\n\t\t}\n\n\t\treturn res;\n    }\n```\n\n
[]