Java DP solution, O(n) time, O(1) space
We create a dp value to track the sum of countUniqueChars(s) results for all s ending at last position. We also use a hashMap to store the last position and sec
We create a dp value to track the sum of countUniqueChars(s) results for all s ending at last position. We also use a hashMap to store the last position and second last position for a certain charactor.\n\nFor example, for the String "ABCDECFGCH", we have \'C\' at 2rd, 5th and 8th position. When it comes to the 3rd \'C\': \n1. The substrings between last \'C\' (excluded) and current \'C\' (included) are: "FGC", "GC", "C". countUniqueChars(s) results for these substrings should be the corresponding countUniqueChars(s) results of substrings ending with \'G\' ("FG", "G", and "") plus 1, since \'C\' is a new unique character.\n2. The substrings between second last \'C\' (excluded) and current \'C\' (included), without and substrings in 1th senariao ares: "DECFGC", "ECFGC", "CFGC". countUniqueChars(s) results for these substrings should be the corresponding countUniqueChars(s) results of substrings ending with \'G\' ("DECFG", "ECFG", and "CFG") minus 1, since \'C\' is not unique anymore.\n3. The substrings starting at or before the second last \'C\', ending with current \'C\' are: "ABCDECFGC", "BCDECFGC", "CDECFGC". countUniqueChars(s) results for these substrings should be the same as the corresponding countUniqueChars(s) results of substrings ending with \'G\' ("ABCDECFG", "BCDECFG", and "BCDECFG"), since \'C\' was already treated as a non-unique character before, and the new \'C\' is not changing anything to the countUniqueChars(s) result.\n\nAs the result of the above 3 cases, if c is the ith character in s: \n`sum( countUniqueChars( substrings ending at i ) ) = sum( countUniqueChars( substrings ending at (i - 1) ) ) + (i - last position c) - (last positon of c - second last position of c)`\nThis is our state transition equation for dynamic programming. The final result is just the sum of all the dp results for each i.\n\n```\nclass Solution {\n    public int uniqueLetterString(String s) {\n        // dp to store the countUniqueChars(s) of Strings ending at last char.\n        int dp = 1;\n        // HashMap from char to int[last position in s, second last position in s]\n        Map<Character, int[]> hashMap = new HashMap<>();\n        int result = 1;\n        hashMap.put(s.charAt(0), new int[]{0, -1});\n        for (int i = 1; i < s.length(); i++) {\n            char c = s.charAt(i);\n            if (!hashMap.containsKey(c)) {\n                hashMap.put(c, new int[]{-1, -1});\n            }\n            int[] positionArray = hashMap.get(c);\n            int lastPosition = positionArray[0];\n            int secondLastPosition = positionArray[1];\n            dp = dp + (i - lastPosition) - (lastPosition - secondLastPosition);\n            result += dp;\n            positionArray[1] = positionArray[0];\n            positionArray[0] = i;\n        }\n        return result;\n    }\n}\n```
['Dynamic Programming', 'Java']