828. 统计子串中的唯一字符

approach 1

class Solution {
    public int uniqueLetterString(String s) {
        char[] cs = s.toCharArray();
        int n = s.length();
        int[] l = new int[n];
        int[] r = new int[n];
        int[] preIdx = new int[26];
        Arrays.fill(preIdx, -1);
        for (int i = 0; i < n; i++) {
            int u = cs[i] - 'A';
            l[i] = preIdx[u];
            preIdx[u] = i;
        }

        Arrays.fill(preIdx, n);
        for (int i = n-1; i >= 0; i--) {
            int u = cs[i] - 'A';
            r[i] = preIdx[u];
            preIdx[u] = i;
        }

        int cnt = 0;
        for (int i = 0; i < n; i++) {
            cnt += (i - l[i]) * (r[i] - i);
        }
        return cnt;
    }
}

超时，超出内存

class Solution {
    public int uniqueLetterString(String s) {
        int n = s.length();
        int res = 0;
        for (int i = 0; i < n; i++) {
            int[] dp = new int[n];
            int[][] map = new int[n][26];
            for (int j = i; j < n; j++) {
                if (j == i) {
                    map[j][s.charAt(i)-'A'] = 1;
                    dp[j] = 1;
                    res++;
                    continue;
                }
                int c = s.charAt(j)-'A';
                int cnt = map[j-1][c];
                // int cnt = 1;
                if (cnt == 1) {
                    dp[j] = dp[j-1] - 1;
                } else if (cnt > 1) {
                    dp[j] = dp[j-1];
                } else {
                    dp[j] = dp[j-1] + 1;
                }
                map[j] = map[j-1];
                map[j][c]++;
                
                res += dp[j];
            }
        }
        
        return res;
    }
}