You are given a string S of lowercase English alphabets. Let X, be the number of substrings of S consisting of at least I distinct characters.
Task
Determine the value of X[i], for all, where i can take values in the range [1, 26] (both inclusive).
Example
Assumptions
N=4
S = aabc
Approach
The value of X[i] can be calculated as follows:
For i = 1. Every substring of S have at least 1 distinct characters, hence X[i] = num of substrings = 4*(5)/2 = 10.
For i = 2. Substrings [aab, aabc, bc, abc, ab] have at least 2 distinct characters, hence X[i] = 5.
For i = 3. Substrings [aabc, abc] have at least 3 distinct characters, hence X[i] = 2.
For i >= 4. No substrings can have more than 3 distinct characters, hence X[i] = 0.
Therefore, the output array is [10 5 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
Function Description
Complete the DistinctChars function provided in the editor. The function takes the following 2 parameters and returns an array denoting the values of X[i].
N: Represents the length of string S .
S: Represents the string S
Input format
Note: This is the input format that you must use to provide custom input (available above the Compile and Test button).
The first line contains an integer N representing the length of the string.
The second line contains the string S.
Output format
Print a single line containing 26 space-separated integers. The ith integer representing the value of X[i], in the same order.
Constraints
1 < N < 5*10^5
Code snippets (also called starter code/boilerplate code)
This question has code snippets for C, CPP, Java, and Python
Sample input 1
3
abc
Sample output 1
6 3 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Copyright © A++ Code Bootcamp 2023