Unique Characters of Every Substring - Microsoft Top Interview Questions

                        Solution in C++ :

int solve(string s) {
    vector<int> ind(26, -1);
    vector<int> left(s.size(), 0), right(s.size(), 0);
    for (int i = 0; i < s.size(); i++) {
        left[i] = ind[s[i] - 'a'];
        ind[s[i] - 'a'] = i;
    }
    fill(ind.begin(), ind.end(), s.size());
    for (int i = s.size() - 1; i >= 0; i--) {
        right[i] = ind[s[i] - 'a'];
        ind[s[i] - 'a'] = i;
    }
    int mod = 1e9 + 7;
    long res = 0;
    for (int i = 0; i < s.size(); i++) {
        res = (res + ((i - left[i]) * (right[i] - i)) % mod) % mod;
    }
    return res;
}
                    

                        Solution in Java :

import java.util.*;

class Solution {
    public int solve(String s) {
        long MOD = 1000000007L;
        int N = s.length();
        ArrayList<Integer>[] indices = new ArrayList[26];
        for (int i = 0; i < 26; i++) {
            indices[i] = new ArrayList<Integer>();
            indices[i].add(-1);
        }
        for (int i = 0; i < N; i++) {
            indices[s.charAt(i) - 'a'].add(i);
        }
        int[] cur = new int[26];
        for (int i = 0; i < 26; i++) {
            cur[i] = 1;
            indices[i].add(N);
        }

        long ans = 0L;
        for (char c : s.toCharArray()) {
            int n = c - 'a';
            long a = indices[n].get(cur[n] + 1) - indices[n].get(cur[n]);
            long b = indices[n].get(cur[n]) - indices[n].get(cur[n] - 1);

            ans += a * b;
            ans %= MOD;
            cur[n] += 1;
        }

        return (int) (ans);
    }
}
                    

                        Solution in Python : 
                            
class Solution:
    def solve(self, s):
        total = 0
        found = defaultdict(lambda: [-1])

        for c, char in enumerate(s):
            found[char].append(c)

            if len(found[char]) == 2:
                continue

            current = found[char]

            total += (current[-1] - current[-2]) * (current[-2] - current[-3])

        end = len(s)

        for item in found:
            current = found[item]
            total += (end - current[-1]) * (current[-1] - current[-2])

        return total % (10 ** 9 + 7)