828. Unique Letter String

Ref
907. Sum of Subarray Minimums
901. Online Stock Span
891. Sum of Subsequence Widths


Version #2 Map of queue of indices
Time O(S.length())  Space O(#distinct chars)
30.25 %
class Solution {
    public int uniqueLetterString(String S) {
        // A0....A1....A2 A would contribute to UNIQ (A1-A0)*(A2-A1) times
        if (S == null || S.length() == 0) {
            return 0;
        }
        long mod = (long)(1e9 + 7);
        long result = 0;
        Map<Character, Queue<Integer>> map = new HashMap<>();
        for (int i = 0; i < S.length(); i++) {
            char curr = S.charAt(i);
            Queue<Integer> que = map.getOrDefault(curr, new LinkedList<>(Arrays.asList(-1)));
            que.offer(i);
            if (que.size() > 2) {
                result = (result + (long)(-que.poll() + que.peek()) * (long)(i - que.peek())) % mod;
            }
            map.put(curr, que);
        }
        int len = S.length();
        for (Queue<Integer> que : map.values()) {
            result = (result + (long)(-que.poll() + que.peek()) * (long)(len - que.peek())) % mod;
        }
        return (int) result;
    }
}


Version #1 List of List of lastIndex

56.96 %
class Solution {
    public int uniqueLetterString(String S) {
        // "ABC"
        // left [0, 1] right[1, 2] -> all substring containing unique B -> 2 * 2 = 4
        // left [0, 0] right[0, 2] -> all substring cotaining unique A -> 1 * 3 = 3
        // "ABA"
        // A -> left[0, 0] right[0, 1] -> 1 * 2 = 2
        // B -> left[0, 1] right[1, 2] -> 2 * 2 = 4
        // A -> left[1, 2] right[2, 2] -> 2 * 1 = 2
        List<List<Integer>> lastIndex = new ArrayList<>();
        for (int i = 0; i < 26; i++) {
            lastIndex.add(new ArrayList<>());
        }
        for (int i = 0; i < S.length(); i++) {
            char c = S.charAt(i);
            lastIndex.get(c - 'A').add(i);
        }
        int result = 0;
        for (int i = 0; i < 26; i++) {
            List<Integer> indices = lastIndex.get(i);
            int prev = -1;
            int curr = 0;
            int next = 0;
            for (int j = 0; j < indices.size(); j++) {
                curr = j == 0 ? indices.get(0) : next;
                next = j == indices.size() - 1 ? S.length() : indices.get(j + 1);
                result += (curr - prev) * (next - curr);
                prev = curr;
            }
        }
        return result;
    }
}