# Unique Characters of Every Substring - Microsoft Top Interview Questions

### Problem Statement :

```Given a lowercase alphabet string s, return the sum of the number of characters that are unique in every substring of s.

Mod the result by 10 ** 9 + 7.

Constraints

n ≤ 100,000 where n is the length of s

Example 1

Input

s = "aab"

Output

6

Explanation

Here are the substrings and their counts:

"a" - 1

"a" - 1

"b" - 1

"aa" - 0 (since "a" is not unique)

"ab" - 2

"aab" - 1 ("since "a" is not unique)```

### Solution :

```                        ```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;
for (int i = 0; i < 26; i++) {
indices[i] = new ArrayList<Integer>();
}
for (int i = 0; i < N; i++) {
}
int[] cur = new int;
for (int i = 0; i < 26; i++) {
cur[i] = 1;
}

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])

```

## Tree Coordinates

We consider metric space to be a pair, , where is a set and such that the following conditions hold: where is the distance between points and . Let's define the product of two metric spaces, , to be such that: , where , . So, it follows logically that is also a metric space. We then define squared metric space, , to be the product of a metric space multiplied with itself: . For

## Array Pairs

Consider an array of n integers, A = [ a1, a2, . . . . an] . Find and print the total number of (i , j) pairs such that ai * aj <= max(ai, ai+1, . . . aj) where i < j. Input Format The first line contains an integer, n , denoting the number of elements in the array. The second line consists of n space-separated integers describing the respective values of a1, a2 , . . . an .

## Self Balancing Tree

An AVL tree (Georgy Adelson-Velsky and Landis' tree, named after the inventors) is a self-balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property. We define balance factor for each node as : balanceFactor = height(left subtree) - height(righ

## Array and simple queries

Given two numbers N and M. N indicates the number of elements in the array A[](1-indexed) and M indicates number of queries. You need to perform two types of queries on the array A[] . You are given queries. Queries can be of two types, type 1 and type 2. Type 1 queries are represented as 1 i j : Modify the given array by removing elements from i to j and adding them to the front. Ty