Find frequency of all characters across all substrings of given string

Given a string S containing all lowercase characters and its length N. Find frequency of all characters across all substrings of the given string.

Examples:

Input: N = 3, S = "aba"
Output:
a 6
b 4
Explanation: The substrings are: a, b, a, ab, ba, aba. The frequency of each character: a = 6, b = 4. Hence the output is "a 6" and "b 4".

Input: N=10, S="ccdbccbbca"
Output:
a 10
b 80
c 106
d 24

Input: N=8, S="dddbabcd"
Output:
a 20
b 38
c 14
d 48

Approach: To solve the problem, follow the below idea:

The problem can be solved by finding the contribution of each character across all substrings. Let's say, a character ch is present at any index idx then this character will occur in all the substrings that start at index <= idx and end at index >= idx. So, this character will contribute one occurrence in all these subtrings.

The count of such substrings can be calculated using Combinatorics. For the starting index, we have total (idx + 1) choices ranging from (0 to idx) and for the ending index, we have total (N - idx) choices ranging from (idx, N - 1). So, the total number of such substrings will be: (idx + 1) * (N - idx). In all these substrings, character ch will occur at least once. Similarly, we can find the contribution of all the characters to get the final answer.

Step-by-step algorithm:

• Run a loop to iterate over the entire string.
• For each index idx, count the number of starting indices for subarrays that contain S[idx] in them, that is (idx + 1).
• For each index idx, count the number of ending indices for subarrays that contain S[idx] in them, that is (N - idx).
• In order to get all the possible subarrays multiply the number of possible starting indices with number of possible ending indices.
• Similarly, count the contribution of all characters at every index to get the final answer.

import java.util.Arrays; public class AllCharOccurencesInAllSubstrings {  // function to count the contribution of every character  static void allCharOccurrencesInAllSubstrings(  String S, int N, long[] freq) {  for (int idx = 0; idx < N; idx++) {  char ch = S.charAt(idx);  // count subarrays containing the character at index  // idx  long count = (idx + 1L) * (N - idx);  freq[ch - 'a'] += count;  }  }  public static void main(String[] args) {  // Sample Input  String S = "ccdbccbbca";  long[] freq = new long[26];  Arrays.fill(freq, 0);  allCharOccurrencesInAllSubstrings(S, S.length(), freq);  for (char ch = 'a'; ch <= 'z'; ch++) {  if (freq[ch - 'a'] > 0)  System.out.println(ch + " " + freq[ch - 'a']);  }  } } // This code is contributed by shivamgupta0987654321 

// Function to count the contribution of every character function allCharOccurrencesInAllSubstrings(S, N, freq) {  for (let idx = 0; idx < N; idx++) {  let ch = S.charAt(idx);  // count subarrays containing the character at index idx  let count = (idx + 1) * (N - idx);  freq[ch.charCodeAt(0) - 'a'.charCodeAt(0)] += count;  } } // Main function function main() {  // Sample Input  let S = "ccdbccbbca";  let freq = new Array(26).fill(0);  allCharOccurrencesInAllSubstrings(S, S.length, freq);  for (let ch = 'a'.charCodeAt(0); ch <= 'z'.charCodeAt(0); ch++) {  if (freq[ch - 'a'.charCodeAt(0)] > 0)  console.log(String.fromCharCode(ch) + " " + freq[ch - 'a'.charCodeAt(0)]);  } } // Call the main function main(); 

#include <bits/stdc++.h> using namespace std; // function to count the contribution of every character void AllCharOccurencesInAllSubtrings(  string S, int N, vector<long long>& freq) {  for (int idx = 0; idx < N; idx++) {  char ch = S[idx];  // count subarrays containing the character at index  // idx  long long count = (idx + 1) * (N - idx);  freq[ch - 'a'] += count;  } } int main() {  // Sample Input  string S = "ccdbccbbca";  vector<long long> freq(26, 0);  AllCharOccurencesInAllSubtrings(S, S.length(), freq);  for (char ch = 'a'; ch <= 'z'; ch++) {  if (freq[ch - 'a'] > 0)  cout << ch << " " << freq[ch - 'a'] << endl;  }  return 0; } // this code is contributed by prophet1999 

# function to count the contribution of every character def all_char_occurrences_in_all_substrings(S, N, freq): for idx in range(N): ch = S[idx] # count subarrays containing the character at index idx count = (idx + 1) * (N - idx) freq[ord(ch) - ord('a')] += count # Sample Input S = "ccdbccbbca" freq = [0] * 26 # Call the function to count character occurrences in all substrings all_char_occurrences_in_all_substrings(S, len(S), freq) # Print the result for ch in range(ord('a'), ord('z') + 1): if freq[ch - ord('a')] > 0: print(chr(ch), freq[ch - ord('a')]) 

a 10 b 80 c 106 d 24

Time Complexity: O(N), where N is the length of input string S.
Auxiliary Space: O(1)