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[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)
View More Similar Problems
Minimum Average Waiting Time
Tieu owns a pizza restaurant and he manages it in his own way. While in a normal restaurant, a customer is served by following the first-come, first-served rule, Tieu simply minimizes the average waiting time of his customers. So he gets to decide who is served first, regardless of how sooner or later a person comes. Different kinds of pizzas take different amounts of time to cook. Also, once h
View Solution →Merging Communities
People connect with each other in a social network. A connection between Person I and Person J is represented as . When two persons belonging to different communities connect, the net effect is the merger of both communities which I and J belongs to. At the beginning, there are N people representing N communities. Suppose person 1 and 2 connected and later 2 and 3 connected, then ,1 , 2 and 3 w
View Solution →Components in a graph
There are 2 * N nodes in an undirected graph, and a number of edges connecting some nodes. In each edge, the first value will be between 1 and N, inclusive. The second node will be between N + 1 and , 2 * N inclusive. Given a list of edges, determine the size of the smallest and largest connected components that have or more nodes. A node can have any number of connections. The highest node valu
View Solution →Kundu and Tree
Kundu is true tree lover. Tree is a connected graph having N vertices and N-1 edges. Today when he got a tree, he colored each edge with one of either red(r) or black(b) color. He is interested in knowing how many triplets(a,b,c) of vertices are there , such that, there is atleast one edge having red color on all the three paths i.e. from vertex a to b, vertex b to c and vertex c to a . Note that
View Solution →Super Maximum Cost Queries
Victoria has a tree, T , consisting of N nodes numbered from 1 to N. Each edge from node Ui to Vi in tree T has an integer weight, Wi. Let's define the cost, C, of a path from some node X to some other node Y as the maximum weight ( W ) for any edge in the unique path from node X to Y node . Victoria wants your help processing Q queries on tree T, where each query contains 2 integers, L and
View Solution →Contacts
We're going to make our own Contacts application! The application must perform two types of operations: 1 . add name, where name is a string denoting a contact name. This must store name as a new contact in the application. find partial, where partial is a string denoting a partial name to search the application for. It must count the number of contacts starting partial with and print the co
View Solution →