Program to find second most frequent character
Given a string, find the second most frequent character in it. Expected time complexity is O(n) where n is the length of the input string.
Examples:
Input: str = "aabababa";
Output: Second most frequent character is 'b'
Input: str = "w3wiki";
Output: Second most frequent character is 'g'
Input: str = "Beginnerquiz";
Output: Second most frequent character is 'g'
The output can also be any other character with
count 1 like 'z', 'i'.
Input: str = "abcd";
Output: No Second most frequent character
A simple solution is to start from the first character, count its occurrences, then second character, and so on. While counting these occurrences keep track of max and second max. Time complexity of this solution is O(n2).
We can solve this problem in O(n) time using a count array with a size equal to 256 (Assuming characters are stored in ASCII format). Following is the implementation of the approach.
Implementation:
C++
#include <bits/stdc++.h> using namespace std; #define NO_OF_CHARS 256 // CPP function to find the // second most frequent character // in a given string 'str' char getSecondMostFreq(string str) { // count number of occurrences of every character. int count[NO_OF_CHARS] = {0}, i; for (i = 0; str[i]; i++) (count[str[i]])++; // Traverse through the count[] and // find second highest element. int first = 0, second = 0; for (i = 0; i < NO_OF_CHARS; i++) { /* If current element is smaller than first then update both first and second */ if (count[i] > count[first]) { second = first; first = i; } /* If count[i] is in between first and second then update second */ else if (count[i] > count[second] && count[i] != count[first]) second = i; } return second; } // Driver code int main() { string str = "w3wiki" ; char res = getSecondMostFreq(str); if (res != '\0' ) cout << "Second most frequent char is " << res; else cout << "No second most frequent character" ; return 0; } // This code is contributed by rathbhupendra |
C
#include <stdio.h> #define NO_OF_CHARS 256 // C function to find the second most frequent character // in a given string 'str' char getSecondMostFreq( char *str) { // count number of occurrences of every character. int count[NO_OF_CHARS] = {0}, i; for (i=0; str[i]; i++) (count[str[i]])++; // Traverse through the count[] and find second highest element. int first = 0, second = 0; for (i = 0; i < NO_OF_CHARS; i++) { /* If current element is smaller than first then update both first and second */ if (count[i] > count[first]) { second = first; first = i; } /* If count[i] is in between first and second then update second */ else if (count[i] > count[second] && count[i] != count[first]) second = i; } return second; } // Driver program to test above function int main() { char str[] = "w3wiki" ; char res = getSecondMostFreq(str); if (res != '\0' ) printf ( "Second most frequent char is %c" , res); else printf ( "No second most frequent character" ); return 0; } |
Java
// Java Program to find the second // most frequent character in a given string public class GFG { static final int NO_OF_CHARS = 256 ; // finds the second most frequently occurring // char static char getSecondMostFreq(String str) { // count number of occurrences of every // character. int [] count = new int [NO_OF_CHARS]; int i; for (i= 0 ; i< str.length(); i++) (count[str.charAt(i)])++; // Traverse through the count[] and find // second highest element. int first = 0 , second = 0 ; for (i = 0 ; i < NO_OF_CHARS; i++) { /* If current element is smaller than first then update both first and second */ if (count[i] > count[first]) { second = first; first = i; } /* If count[i] is in between first and second then update second */ else if (count[i] > count[second] && count[i] != count[first]) second = i; } return ( char )second; } // Driver program to test above function public static void main(String args[]) { String str = "w3wiki" ; char res = getSecondMostFreq(str); if (res != '\0' ) System.out.println( "Second most frequent char" + " is " + res); else System.out.println( "No second most frequent" + "character" ); } } // This code is contributed by Sumit Ghosh |
Python 3
# Python 3 Program to find the # second most frequent character # in a given string # Function to find the second # most frequent character # in a given string 'str' def getSecondMostFreq( str ) : NO_OF_CHARS = 256 # Initialize count list of # 256 size with value 0 count = [ 0 ] * NO_OF_CHARS # count number of occurrences # of every character. for i in range ( len ( str )) : count[ ord ( str [i])] + = 1 first, second = 0 , 0 # Traverse through the count[] # and find second highest element. for i in range (NO_OF_CHARS) : # If current element is smaller # than first then update both # first and second if count[i] > count[first] : second = first first = i # If count[i] is in between # first and second # then update second */ elif (count[i] > count[second] and count[i] ! = count[first] ) : second = i # return character return chr (second) # Driver code if __name__ = = "__main__" : str = "w3wiki" # function calling res = getSecondMostFreq( str ) if res ! = '\0' : print ( "Second most frequent char is" , res) else : print ( "No second most frequent character" ) # This code is contributed by ANKITRAI1 |
C#
// C# Program to find the second most frequent // character in a given string using System; public class GFG { static int NO_OF_CHARS = 256; // finds the second most frequently // occurring char static char getSecondMostFreq( string str) { // count number of occurrences of every // character. int []count = new int [NO_OF_CHARS]; for ( int i = 0; i < str.Length; i++) (count[str[i]])++; // Traverse through the count[] and find // second highest element. int first = 0, second = 0; for ( int i = 0; i < NO_OF_CHARS; i++) { /* If current element is smaller than first then update both first and second */ if (count[i] > count[first]) { second = first; first = i; } /* If count[i] is in between first and second then update second */ else if (count[i] > count[second] && count[i] != count[first]) second = i; } return ( char )second; } // Driver program to test above function public static void Main() { string str = "w3wiki" ; char res = getSecondMostFreq(str); if (res != '\0' ) Console.Write( "Second most frequent char" + " is " + res); else Console.Write( "No second most frequent" + "character" ); } } // This code is contributed by nitin mittal. |
Javascript
<script> // JavaScript Program to find // the second most frequent // character in a given string let NO_OF_CHARS = 256; // finds the second most frequently // occurring char function getSecondMostFreq(str) { // count number of occurrences of every // character. let count = new Array(NO_OF_CHARS); count.fill(0); for (let i = 0; i < str.length; i++) (count[str[i].charCodeAt()])++; // Traverse through the count[] and find // second highest element. let first = 0, second = 0; for (let i = 0; i < NO_OF_CHARS; i++) { /* If current element is smaller than first then update both first and second */ if (count[i] > count[first]) { second = first; first = i; } /* If count[i] is in between first and second then update second */ else if (count[i] > count[second] && count[i] != count[first]) second = i; } return String.fromCharCode(second); } let str = "w3wiki" ; let res = getSecondMostFreq(str); if (res != '\0' ) document.write( "Second most frequent char" + " is " + res); else document.write( "No second most frequent" + "character" ); </script> |
PHP
<?php $NO_OF_CHARS =256; // PHP function to find the // second most frequent character // in a given string 'str' function getSecondMostFreq( $str ) { global $NO_OF_CHARS ; // count number of occurrences of every character. $count = array_fill (0, $NO_OF_CHARS ,0); for ( $i = 0; $i < strlen ( $str ); $i ++) $count [ord( $str [ $i ])]++; // Traverse through the count[] and // find second highest element. $first = $second = 0; for ( $i = 0; $i < $NO_OF_CHARS ; $i ++) { /* If current element is smaller than first then update both first and second */ if ( $count [ $i ] > $count [ $first ]) { $second = $first ; $first = $i ; } /* If count[i] is in between first and second then update second */ else if ( $count [ $i ] > $count [ $second ] && $count [ $i ] != $count [ $first ]) $second = $i ; } return chr ( $second ); } // Driver code $str = "w3wiki" ; $res = getSecondMostFreq( $str ); if ( strlen ( $res )) echo "Second most frequent char is " . $res ; else echo "No second most frequent character" ; // This code is contributed by mits ?> |
Second most frequent char is g
Time Complexity: O(N), as we are using a loop for traversing the string.
Auxiliary Space: O(256), as we are using extra space for count array.
Approach#2: Using counter
This approach code uses the Counter class from the collections module to count the frequencies of each character in the input string. It then creates a list of tuples from the Counter object, sorts it by frequency in descending order, and returns the character with the second highest frequency (if there is one).
Algorithm
1. Define the input string.
2. Import the Counter class from the collections module and use it to count the frequencies of each character in the string.
3. Create a list of tuples from the Counter object, with each tuple containing a character and its frequency.
4. Sort the list by frequency in descending order.
5. Return the second element of the list (i.e., the character with the second highest frequency)
C++
#include <algorithm> #include <iostream> #include <map> // Function to find the second most frequent // character char second_most_frequent_char(std::string s) { std::map< char , int > freqs; for ( char c : s) { freqs++; } // Lambda Function auto cmp = []( const std::pair< char , int >& a, const std::pair< char , int >& b) { return a.second > b.second; }; std::vector<std::pair< char , int > > sorted_freqs( freqs.begin(), freqs.end()); std::sort(sorted_freqs.begin(), sorted_freqs.end(), cmp); return sorted_freqs.size() > 1 ? sorted_freqs[1].first : '\0' ; } // Driver Code int main() { std::string s = "w3wiki" ; std::cout << second_most_frequent_char(s) << std::endl; return 0; } |
Java
// Java code to implement the above approach import java.util.*; public class GFG { public static char secondMostFrequentChar(String s) { Map<Character, Integer> freqs = new HashMap<>(); // Count the frequencies of characters for ( char c : s.toCharArray()) { freqs.put(c, freqs.getOrDefault(c, 0 ) + 1 ); } // Sort the frequencies in descending order List<Map.Entry<Character, Integer> > sortedFreqs = new ArrayList<>(freqs.entrySet()); Collections.sort( sortedFreqs, (a, b) -> b.getValue().compareTo(a.getValue())); // Check if there is a second most frequent // character if (sortedFreqs.size() > 1 ) { return sortedFreqs.get( 2 ).getKey(); } else { return '\0' ; // Return null character if there // is no second most frequent // character } } public static void main(String[] args) { String s = "w3wiki" ; char secondMostFreqChar = secondMostFrequentChar(s); System.out.println(secondMostFreqChar); } } // This code is contributed by Susobhan Akhuli |
Python3
from collections import Counter def second_most_frequent_char(s): freqs = Counter(s) sorted_freqs = sorted (freqs.items(), key = lambda x: x[ 1 ], reverse = True ) return sorted_freqs[ 1 ][ 0 ] if len (sorted_freqs) > 1 else None s = "w3wiki" print (second_most_frequent_char(s)) |
C#
using System; using System.Collections.Generic; using System.Linq; class Program { // Define a function to find the second most frequent character in a string static char ? SecondMostFrequentChar( string s) { // Create a dictionary to store character frequencies Dictionary< char , int > freqs = new Dictionary< char , int >(); // Count the frequency of each character in the input string foreach ( char c in s) { if (freqs.ContainsKey(c)) { freqs++; } else { freqs = 1; } } // Sort the dictionary by frequency in descending order var sortedFreqs = freqs.OrderByDescending(pair => pair.Value); // Check if there is at least a second most frequent character if (sortedFreqs.Count() > 1) { // Return the character with the second highest frequency return sortedFreqs.ElementAt(1).Key; } else { // If there is no second most frequent character, return null return null ; } } // Test the function with a sample string static void Main() { string s = "w3wiki" ; Console.WriteLine(SecondMostFrequentChar(s)); // Output: 'g' } } |
Javascript
// Define a function to find the second most frequent character in a string function secondMostFrequentChar(s) { // Create an empty object to store character frequencies const freqs = {}; // Count the frequency of each character in the input string for (const char of s) { if (freqs[char]) { freqs[char]++; } else { freqs[char] = 1; } } // Convert the frequency object into an array of key-value pairs const sortedFreqs = Object.entries(freqs); // Sort the key-value pairs based on frequency in descending order sortedFreqs.sort((a, b) => b[1] - a[1]); // Check if there is at least a second most frequent character if (sortedFreqs.length > 1) { // Return the character with the second highest frequency return sortedFreqs[1][0]; } else { // If there is no second most frequent character, return null return null ; } } // Test the function with a sample string const s = "w3wiki" ; console.log(secondMostFrequentChar(s)); // Output: "g" |
g
Time Complexity:
The time complexity of this program is O(n log n), where n is the length of the input string. This is because we need to sort the list of character frequencies, which takes O(n log n) time using the built-in sorted() function in Python. The other operations in the program take O(n) time.
Space Complexity:
The space complexity of this program is O(n), where n is the number of distinct characters in the input string. This is because we need to store each character and its frequency in the Counter object.
Contact Us