O(N) Easy Understanding Java Solution with Explanation
Firstly, we maintain a HashMap to save the position of every character. \nTaking LETTER for example, the HashMap will be like this:\n\n\'L\': <0>\n\'E\': <1,4>\
Firstly, we maintain a `HashMap` to save the position of every character. \nTaking `LETTER` for example, the `HashMap` will be like this:\n```\n\'L\': <0>\n\'E\': <1,4>\n\'T\': <2,3>\n\'R\': <5>\n```\nInstead of calculating every substring\'s `UNIQ()`, we calculate every character respectively.\nFor the first `E` in `LETTER`,  the substring contains this `E` as a unique character have four parts: \n\nitself: `E`\nleft: `LE`\nright: `ET`, `ETT`\ncombination of left and right:  `LET`, `LETT`\n\nWe can calculate the distance between this `E` and previous/next `E`  by the above `HashMap`, let\'s say `left` and `right`.\nThe number of  the substring contains this `E` as a unique character will be:\n`\n1 + left + right + left * right\n`\nWe calculate this for every character and the summation is the result.\nHere is the code in Java:\n```\nclass Solution {\n    public int uniqueLetterString(String S) {\n        Map<Character, ArrayList<Integer>> h = new HashMap<>();\n        char[] ca= S.toCharArray();\n        for (int i = 0; i < S.length(); i++) {\n            ArrayList<Integer> l = h.getOrDefault(ca[i], new ArrayList<>());\n            l.add(i);\n            h.put(ca[i], l);\n        }\n        int sum  = 0;\n        for (Map.Entry<Character, ArrayList<Integer>> entry : h.entrySet()) {\n            ArrayList<Integer> l = entry.getValue();\n            for (int i = 0; i < l.size(); i++) {\n                int left = i == 0 ? l.get(i) : l.get(i) - l.get(i - 1) - 1;\n                int right = i == l.size() - 1 ? S.length() - l.get(i) - 1 : l.get(i + 1) - l.get(i) - 1;\n                sum = (sum + 1 + left + right + left * right) % 1000000007;\n            }\n        }\n        return sum;\n    }\n} \n```
[]