Given a string S consisting of lowercase alphabets of size N, the task is to count all substrings which contain the most frequent character in the string as the first character.
Note: If more than one character has a maximum frequency, consider the lexicographically smallest among them.
Examples:
Input: S = “abcab”
Output: 7
Explanation:
There are two characters a and b occurring maximum times i.e., 2 times.
Selecting the lexicographically smaller character i.e. ‘a’.
Substrings starts with ‘a’ are: “a”, “ab”, “abc”, “abca”, “abcab”, “a”, “ab”.
Therefore the count is 7.Input: S= “cccc”
Output: 10
Approach: The idea is to first find the character that occurs the maximum number of times and then count the substring starting with that character in the string. Follow the steps below to solve the problem:
- Initialize the count as 0 that will store the total count of strings.
- Find the maximum occurring character in the string S. Let that character be ch.
- Traverse the string using the variable i and if the character at ith index is the same as ch, increment the count by (N – i).
- After the above steps, print the value of count as the result.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include<bits/stdc++.h>using namespace std;// Function to find all substrings// whose first character occurs// maximum number of timesint substringCount(string s){ // Stores frequency of characters vector<int> freq(26, 0); // Stores character that appears // maximum number of times char max_char = '#'; // Stores max frequency of character int maxfreq = INT_MIN; // Updates frequency of characters for(int i = 0; i < s.size(); i++) { freq[s[i] - 'a']++; // Update maxfreq if (maxfreq < freq[s[i] - 'a']) maxfreq = freq[s[i] - 'a']; } // Character that occurs // maximum number of times for(int i = 0; i < 26; i++) { // Update the maximum frequency // character if (maxfreq == freq[i]) { max_char = (char)(i + 'a'); break; } } // Stores all count of substrings int ans = 0; // Traverse over string for(int i = 0; i < s.size(); i++) { // Get the current character char ch = s[i]; // Update count of substrings if (max_char == ch) { ans += (s.size() - i); } } // Return the count of all // valid substrings return ans;}// Driver Codeint main(){ string S = "abcab"; // Function Call cout << (substringCount(S));}// This code is contributed by mohit kumar 29 |
Java
// Java program for the above approachimport java.util.*;class GFG { // Function to find all substrings // whose first character occurs // maximum number of times static int substringCount(String s) { // Stores frequency of characters int[] freq = new int[26]; // Stores character that appears // maximum number of times char max_char = '#'; // Stores max frequency of character int maxfreq = Integer.MIN_VALUE; // Updates frequency of characters for (int i = 0; i < s.length(); i++) { freq[s.charAt(i) - 'a']++; // Update maxfreq if (maxfreq < freq[s.charAt(i) - 'a']) maxfreq = freq[s.charAt(i) - 'a']; } // Character that occurs // maximum number of times for (int i = 0; i < 26; i++) { // Update the maximum frequency // character if (maxfreq == freq[i]) { max_char = (char)(i + 'a'); break; } } // Stores all count of substrings int ans = 0; // Traverse over string for (int i = 0; i < s.length(); i++) { // Get the current character char ch = s.charAt(i); // Update count of substrings if (max_char == ch) { ans += (s.length() - i); } } // Return the count of all // valid substrings return ans; } // Driver Code public static void main(String[] args) { String S = "abcab"; // Function Call System.out.println(substringCount(S)); }} |
Python3
# Python3 program for the above approach import sys# Function to find all substrings# whose first character occurs# maximum number of timesdef substringCount(s): # Stores frequency of characters freq = [0 for i in range(26)] # Stores character that appears # maximum number of times max_char = '#' # Stores max frequency of character maxfreq = -sys.maxsize - 1 # Updates frequency of characters for i in range(len(s)): freq[ord(s[i]) - ord('a')] += 1 # Update maxfreq if (maxfreq < freq[ord(s[i]) - ord('a')]): maxfreq = freq[ord(s[i]) - ord('a')] # Character that occurs # maximum number of times for i in range(26): # Update the maximum frequency # character if (maxfreq == freq[i]): max_char = chr(i + ord('a')) break # Stores all count of substrings ans = 0 # Traverse over string for i in range(len(s)): # Get the current character ch = s[i] # Update count of substrings if (max_char == ch): ans += (len(s) - i) # Return the count of all # valid substrings return ans# Driver Codeif __name__ == '__main__': S = "abcab" # Function Call print(substringCount(S))# This code is contributed by ipg2016107 |
C#
// C# program for the above approachusing System; class GFG{ // Function to find all substrings// whose first character occurs// maximum number of timesstatic int substringCount(string s){ // Stores frequency of characters int[] freq = new int[26]; // Stores character that appears // maximum number of times char max_char = '#'; // Stores max frequency of character int maxfreq = Int32.MinValue; // Updates frequency of characters for(int i = 0; i < s.Length; i++) { freq[s[i] - 'a']++; // Update maxfreq if (maxfreq < freq[s[i] - 'a']) maxfreq = freq[s[i] - 'a']; } // Character that occurs // maximum number of times for(int i = 0; i < 26; i++) { // Update the maximum frequency // character if (maxfreq == freq[i]) { max_char = (char)(i + 'a'); break; } } // Stores all count of substrings int ans = 0; // Traverse over string for(int i = 0; i < s.Length; i++) { // Get the current character char ch = s[i]; // Update count of substrings if (max_char == ch) { ans += (s.Length - i); } } // Return the count of all // valid substrings return ans;}// Driver Codepublic static void Main(){ string S = "abcab"; // Function Call Console.WriteLine(substringCount(S));}}// This code is contributed by susmitakundugoaldanga |
Javascript
<script>// JavaScript program for the above approach// Function to find all substrings// whose first character occurs// maximum number of timesfunction substringCount(s) { // Stores frequency of characters var freq = new Array(26).fill(0); // Stores character that appears // maximum number of times var max_char = "#"; // Stores max frequency of character var maxfreq = -21474836487; // Updates frequency of characters for(var i = 0; i < s.length; i++) { freq[s[i].charCodeAt(0) - "a".charCodeAt(0)]++; // Update maxfreq if (maxfreq < freq[s[i].charCodeAt(0) - "a".charCodeAt(0)]) maxfreq = freq[s[i].charCodeAt(0) - "a".charCodeAt(0)]; } // Character that occurs // maximum number of times for(var i = 0; i < 26; i++) { // Update the maximum frequency // character if (maxfreq === freq[i]) { max_char = String.fromCharCode( i + "a".charCodeAt(0)); break; } } // Stores all count of substrings var ans = 0; // Traverse over string for(var i = 0; i < s.length; i++) { // Get the current character var ch = s[i]; // Update count of substrings if (max_char === ch) { ans += s.length - i; } } // Return the count of all // valid substrings return ans;}// Driver Codevar S = "abcab";// Function Calldocument.write(substringCount(S));// This code is contributed by rdtank</script> |
Output:
7
Time Complexity: O(N), as we are using a loop to traverse the string.
Auxiliary Space: O(1), as we are using freq array of size 26 which is constant.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
