Given string str. The task is to find the maximum occurring character in the string str.
Examples:
Input: neveropen
Output: e
Explanation: ‘e’ occurs 4 times in the stringInput: test
Output: t
Explanation: ‘t’ occurs 2 times in the string
Return the maximum occurring character in an input string using Hashing:
Naive approach : ( using unordered_map )
In this approach we simply use the unordered_map from STL to store the frequency of every character and while adding characters to map we take a variable count to determine the element having highest frequency.
Implementation :
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// function that return maximum occurring characterchar getMaxOccurringChar(string str){ // create unordered_map to store frequency of every character unordered_map<char,int>mp; // to store length of string int n = str.length(); // to store answer char ans; // to check count of answer character is less or greater // than another elements count int cnt=0; // traverse the string for(int i=0 ;i<n ; i++){ // push element into map and increase its frequency mp[str[i]]++; // update answer and count if(cnt < mp[str[i]]){ ans = str[i]; cnt = mp[str[i]]; } } return ans; }// Driver Codeint main(){ string str = "sample string"; cout << "Max occurring character is: " << getMaxOccurringChar(str);}// this code is contributed by bhardwajji |
Java
import java.util.*;public class Main { // function that returns maximum occurring character static char getMaxOccurringChar(String str) { // create HashMap to store frequency of every character HashMap<Character, Integer> mp = new HashMap<>(); // to store length of string int n = str.length(); // to store answer char ans = 0; // to check count of answer character is less or greater // than another elements count int cnt = 0; // traverse the string for(int i = 0; i < n; i++) { // push element into map and increase its frequency char c = str.charAt(i); mp.put(c, mp.getOrDefault(c, 0) + 1); // update answer and count if(cnt < mp.get(c)) { ans = c; cnt = mp.get(c); } } return ans; } // Driver Code public static void main(String[] args) { String str = "sample string"; System.out.println("Max occurring character is: " + getMaxOccurringChar(str)); }}// This code is contributed by kalyanbef |
Python3
# function that return maximum occurring characterdef getMaxOccurringChar(str): # create dictionary to store frequency of every character mp = {} # to store length of string n = len(str) # to store answer ans = '' # to check count of answer character is less or greater # than another elements count cnt = 0 # traverse the string for i in range(n): # push element into dictionary and increase its frequency if str[i] in mp: mp[str[i]] += 1 else: mp[str[i]] = 1 # update answer and count if cnt < mp[str[i]]: ans = str[i] cnt = mp[str[i]] return ans# Driver Codestr = "sample string"print("Max occurring character is:", getMaxOccurringChar(str)) |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class MainClass { public static void Main(string[] args) { string str = "sample string"; Console.WriteLine("Max occurring character is: " + getMaxOccurringChar(str)); } // function that return maximum occurring character static char getMaxOccurringChar(string str) { // create dictionary to store frequency of every // character Dictionary<char, int> mp = new Dictionary<char, int>(); // to store length of string int n = str.Length; // to store answer char ans = '\0'; // to check count of answer character is less or // greater than another elements count int cnt = 0; // traverse the string for (int i = 0; i < n; i++) { // push element into map and increase its // frequency if (mp.ContainsKey(str[i])) { mp[str[i]]++; } else { mp.Add(str[i], 1); } // update answer and count if (cnt < mp[str[i]]) { ans = str[i]; cnt = mp[str[i]]; } } return ans; }} |
Javascript
// JavaScript program for the above approach// function that return maximum occurring characterfunction getMaxOccurringChar(str){ // create map to store frequency of every character let mp = new Map(); // to store length of string let n = str.length; // to store answer let ans; // to check count of answer character is less or greater // than another elements count let cnt=0; // traverse the string for(let i=0 ;i<n ; i++){ // push element into map and increase its frequency mp.set(str[i], (mp.get(str[i]) || 0) + 1); // update answer and count if(cnt < mp.get(str[i])){ ans = str[i]; cnt = mp.get(str[i]); } } return ans;}// Driver Codelet str = "sample string";console.log("Max occurring character is: " + getMaxOccurringChar(str));// This code is contributed by rutikbhosale |
C
#include <stdio.h>#include <stdlib.h>#include <string.h>// Function to find the maximum occurring characterchar getMaxOccurringChar(char str[]){ // Create a hash table (unordered_map) to store the // frequency of each character int count[256] = { 0 }; // Traverse the string and update the frequency of each // character int length = strlen(str); for (int i = 0; i < length; i++) count[(int)str[i]]++; // Find the character with the maximum frequency char maxChar; int maxCount = 0; for (int i = 0; i < length; i++) { if (count[(int)str[i]] > maxCount) { maxCount = count[(int)str[i]]; maxChar = str[i]; } } return maxChar;}// Driver Codeint main(){ char str[] = "sample string"; printf("Max occurring character is: %c\n", getMaxOccurringChar(str)); return 0;} |
Output
Max occurring character is: s
Time Complexity: O(N), Traversing the string of length N one time.
Auxiliary Space: O(N), where N is the size of the string
The idea is to store the frequency of every character in the array and return the character with maximum count.
Follow the steps to solve the problem:
- Create a count array of size 256 to store the frequency of every character of the string
- Maintain a max variable to store the maximum frequency so far whenever encounter a frequency more than the max then update the max
- And update that character in our result variable.
Below is the implementation of the above approach:
C
// C program to output the maximum occurring character// in a string#include <stdio.h>#include <string.h>#define ASCII_SIZE 256char getMaxOccurringChar(char* str){ // Create array to keep the count of individual // characters and initialize the array as 0 int count[ASCII_SIZE] = { 0 }; // Construct character count array from the input // string. int len = strlen(str); int max = 0; // Initialize max count char result; // Initialize result // Traversing through the string and maintaining // the count of each character for (int i = 0; i < len; i++) { count[str[i]]++; if (max < count[str[i]]) { max = count[str[i]]; result = str[i]; } } return result;}// Driver program to test the above functionint main(){ char str[] = "sample string"; printf("Max occurring character is %c", getMaxOccurringChar(str));} |
C++
// C++ program to output the maximum occurring character// in a string#include <bits/stdc++.h>#define ASCII_SIZE 256using namespace std;char getMaxOccurringChar(char* str){ // Create array to keep the count of individual // characters and initialize the array as 0 int count[ASCII_SIZE] = { 0 }; // Construct character count array from the input // string. int len = strlen(str); int max = 0; // Initialize max count char result; // Initialize result // Traversing through the string and maintaining // the count of each character for (int i = 0; i < len; i++) { count[str[i]]++; if (max < count[str[i]]) { max = count[str[i]]; result = str[i]; } } return result;}// Driver program to test the above functionint main(){ char str[] = "sample string"; cout << "Max occurring character is " << getMaxOccurringChar(str);} |
Java
// Java program to output the maximum occurring character// in a stringpublic class GFG { static final int ASCII_SIZE = 256; static char getMaxOccurringChar(String str) { // Create array to keep the count of individual // characters and initialize the array as 0 int count[] = new int[ASCII_SIZE]; // Construct character count array from the input // string. int len = str.length(); for (int i = 0; i < len; i++) count[str.charAt(i)]++; int max = -1; // Initialize max count char result = ' '; // Initialize result // Traversing through the string and maintaining // the count of each character for (int i = 0; i < len; i++) { if (max < count[str.charAt(i)]) { max = count[str.charAt(i)]; result = str.charAt(i); } } return result; } // Driver Method public static void main(String[] args) { String str = "sample string"; System.out.println("Max occurring character is " + getMaxOccurringChar(str)); }} |
Python3
# Python program to return the maximum occurring character in the input stringASCII_SIZE = 256def getMaxOccurringChar(str): # Create array to keep the count of individual characters # Initialize the count array to zero count = [0] * ASCII_SIZE # Utility variables max = -1 c = '' # Traversing through the string and maintaining the count of # each character for i in str: count[ord(i)] += 1 for i in str: if max < count[ord(i)]: max = count[ord(i)] c = i return c# Driver program to test the above functionstr = "sample string"print("Max occurring character is", getMaxOccurringChar(str))# Although this program can be written in atmost 3 lines in Python# the above program has been written for a better understanding of# the reader# Shorter version of the program# import collections# str = "sample string"# print "Max occurring character is " +# collections.Counter(str).most_common(1)[0][0]# This code has been contributed by Bhavya Jain |
C#
// C# program to output the maximum// occurring character in a stringusing System;class GFG { static int ASCII_SIZE = 256; static char getMaxOccurringChar(String str) { // Create array to keep the count of // individual characters and // initialize the array as 0 int[] count = new int[ASCII_SIZE]; // Construct character count array // from the input string. int len = str.Length; for (int i = 0; i < len; i++) count[str[i]]++; int max = -1; // Initialize max count char result = ' '; // Initialize result // Traversing through the string and // maintaining the count of each character for (int i = 0; i < len; i++) { if (max < count[str[i]]) { max = count[str[i]]; result = str[i]; } } return result; } // Driver Method public static void Main() { String str = "sample string"; Console.Write("Max occurring character is " + getMaxOccurringChar(str)); }}// This code is contributed by Sam007 |
PHP
<?php // PHP program to output the maximum // occurring character in a string $ASCII_SIZE = 256; function getMaxOccurringChar($str) { global $ASCII_SIZE; // Create array to keep the count // of individual characters and // initialize the array as 0 $count = array_fill(0, $ASCII_SIZE, NULL); // Construct character count array // from the input string. $len = strlen($str); $max = 0; // Initialize max count // Traversing through the string // and maintaining the count of // each character for ($i = 0; $i < ($len); $i++) { $count[ord($str[$i])]++; if ($max < $count[ord($str[$i])]) { $max = $count[ord($str[$i])]; $result = $str[$i]; } } return $result; } // Driver Code $str = "sample string"; echo "Max occurring character is " . getMaxOccurringChar($str); // This code is contributed by ita_c ?> |
Javascript
<script>// Javascript program to output the maximum occurring character // in a string let ASCII_SIZE = 256; function getMaxOccurringChar(str) { // Create array to keep the count of individual // characters and initialize the array as 0 let count = new Array(ASCII_SIZE); for (let i = 0; i < ASCII_SIZE; i++) { count[i] = 0; } // Construct character count array from the input // string. let len = str.length; for (let i = 0; i < len; i++) { count[str[i].charCodeAt(0)] += 1; } let max = -1; // Initialize max count let result = ' '; // Initialize result // Traversing through the string and maintaining // the count of each character for (let i = 0; i < len; i++) { if (max < count[str[i].charCodeAt(0)]) { max = count[str[i].charCodeAt(0)]; result = str[i]; } } return result; } // Driver Method let str = "sample string"; document.write("Max occurring character is " , getMaxOccurringChar(str)); // This code is contributed by avanitrachhadiya2155</script> |
Output
Max occurring character is s
Time Complexity: O(N), Traversing the string of length N one time.
Auxiliary Space: O(1)
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!
