1D DP Approach
Input : string s of length n\nState : dp[i] stores the sum of unique chars of substrings ending at s[i]\nBase : dp[0] = 1\nRecurrence : dp[i] = dp[i-1] + (i-j) 
**Input** : `string s` of length `n`\n**State** : `dp[i]` stores the sum of unique chars of substrings ending at `s[i]`\n**Base** : `dp[0] = 1`\n**Recurrence** : `dp[i] = dp[i-1] + (i-j) - (j-k)` where`j` & `k` are the _rightmost_ and _second rightmost_ occurence of `s[i]` in subarray `s[0 : i-1]`  respectively, defaulting to `-1` if there are no such occurrences\n**Answer** : `SUM(dp[i])` where `0 <= i < n`\n\n**Explanation** :\nConsider string `s = REPEATCODE`\nAll the substrings ending at `s[9] = E` are :\n```\n         E\n        DE\n       ODE\n      CODE\n     TCODE\n    ATCODE\n   EATCODE\n  PEATCODE\n EPEATCODE\nREPEATCODE\n```\n\nNotice how it contains the substrings ending at `s[8] = D`\n```\n          E\n        D|E\n       OD|E\n      COD|E\n     TCOD|E\n    ATCOD|E\n   EATCOD|E\n  PEATCOD|E\n EPEATCOD|E\nREPEATCOD|E\n```\n\nLet\'s write the change in unique character count happening for each substring on addition of rightmost E\n```\n          E +1\n        D|E +1\n       OD|E +1\n      COD|E +1\n     TCOD|E +1\n    ATCOD|E +1\n   EATCOD|E -1 (since leftmost E is now not unique anymore)\n  PEATCOD|E -1\n EPEATCOD|E  0 (leftmost E was already non-unique)\nREPEATCOD|E  0\n```\n\nLet\'s add `i , j , k` into the picture\n```\ni = 9                E +1\n                   D|E +1\n                  OD|E +1\n                 COD|E +1\n                TCOD|E +1\n               ATCOD|E +1\nj = 3         EATCOD|E -1 (since leftmost E is now not unique anymore)\n             PEATCOD|E -1\nk = 1       EPEATCOD|E  0 (leftmost E was already non-unique)\n           REPEATCOD|E  0\n```\n\nAs is evident from the above diagram , we have to add `+1` 6 times , `-1` 2 times and `0` 2 times to the answer for the string `REPEATCOD` i.e. `dp[i-1]`.\n\nAlso note that 6 times is basically `i - j = 9 - 3` , 2 times is `j - k = 3 - 1` and we can ignore the last one because adding 0 is redundant.\n\nHence, the recurrence formula `dp[i] = dp[i-1] + (i-j) - (j-k)`
['Dynamic Programming']