Given a linked list of characters. The task is to find the maximum occurring character in the linked list. if there are multiple answers, return the first maximum occurring character.
Examples:
Input : g -> e -> e -> k -> s Output : e Input : a -> a -> b -> b -> c -> c -> d -> d Output : d
Method 1: Iteratively count the frequency of each character in a string and return the one which has maximum occurrence.
Implementation:
C++
// C++ program to count the maximum// occurring character in linked list#include <bits/stdc++.h>using namespace std;/* Link list node */struct Node { char data; struct Node *next;};char maxChar(struct Node *head) { struct Node *p = head; int max = -1; char res; while (p != NULL) { // counting the frequency of current element // p->data struct Node *q = p->next; int count = 1; while (q != NULL) { if (p->data == q->data) count++; q = q->next; } // if current counting is greater than max if (max < count) { res = p->data; max = count; } p = p->next; } return res;}/* Push a node to linked list. Note that this function changes the head */void push(struct Node **head_ref, char new_data) { struct Node *new_node = new Node; new_node->data = new_data; new_node->next = (*head_ref); (*head_ref) = new_node;}/* Driver program to test above function*/int main() { /* Start with the empty list */ struct Node *head = NULL; char str[] = "skeegforskeeg"; int i; // this will create a linked list of // character "neveropen" for (i = 0; str[i] != '\0'; i++) push(&head, str[i]); cout << maxChar(head); return 0;} |
Java
// Java program to count the// maximum occurring character // in linked listimport java.util.*;class GFG{// Link list node static class Node { char data; Node next;}; static Node head_ref; static char maxChar(Node head) { Node p = head; int max = -1; char res = '0'; while (p != null) { // counting the frequency // of current element // p.data Node q = p.next; int count = 1; while (q != null) { if (p.data == q.data) count++; q = q.next; } // if current counting // is greater than max if (max < count) { res = p.data; max = count; } p = p.next; } return res;}// Push a node to linked list. // Note that this function // changes the head static void push(char new_data) { Node new_node = new Node(); new_node.data = new_data; new_node.next = head_ref; head_ref = new_node;}// Driver codepublic static void main(String[] args) { // Start with the empty list head_ref = null; String str = "skeegforskeeg"; char st[] = str.toCharArray(); int i; // this will create a linked // list of character "neveropen" for (i = 0; i < st.length; i++) push(st[i]); System.out.print(maxChar(head_ref));}}// This code is contributed by shikhasingrajput |
Python3
# Python program to count the# maximum occurring character# in linked list# Link list Nodeclass Node: def __init__(self, data): self.data = data; self.next = next;head_ref = None;def maxChar(head): p = head; max = -1; res = '0'; while (p != None): # counting the frequency # of current element # p.data q = p.next; count = 1; while (q != None): if (p.data == q.data): count += 1; q = q.next; # if current counting # is greater than max if (max < count): res = p.data; max = count; p = p.next; return res;# Push a Node to linked list.# Note that this function# changes the headdef push(new_data): global head_ref; new_node = Node(0); new_node.data = new_data; new_node.next = head_ref; head_ref = new_node; head_ref = new_node;# Driver codeif __name__ == '__main__': # Start with the empty list head_ref = None; str = "skeegforskeeg"; st = str; i = 0; # this will create a linked # list of character "neveropen" for i in range(len(st)): push(st[i]); print(maxChar(head_ref));# This code is contributed by shikhasingrajput |
C#
// C# program to count the// maximum occurring character // in linked listusing System;class GFG{ // Link list node class Node { public char data; public Node next;}; static Node head_ref; static char maxChar(Node head) { Node p = head; int max = -1; char res = '0'; while (p != null) { // counting the frequency // of current element // p.data Node q = p.next; int count = 1; while (q != null) { if (p.data == q.data) count++; q = q.next; } // if current counting // is greater than max if (max < count) { res = p.data; max = count; } p = p.next; } return res;} // Push a node to linked list. // Note that this function // changes the head static void push(char new_data) { Node new_node = new Node(); new_node.data = new_data; new_node.next = head_ref; head_ref = new_node;} // Driver codepublic static void Main(string[] args) { // Start with the empty list head_ref = null; string str = "skeegforskeeg"; char []st = str.ToCharArray(); int i; // this will create a linked // list of character "neveropen" for (i = 0; i < st.Length; i++) push(st[i]); Console.Write(maxChar(head_ref));}}// This code is contributed by rutvik_56 |
Javascript
<script>// Javascript program to count the// maximum occurring character // in linked list // Link list node class Node { constructor() { this.data = ''; this.next = null; }}; var head_ref = null; function maxChar( head) { var p = head; var max = -1; var res = '0'; while (p != null) { // counting the frequency // of current element // p.data var q = p.next; var count = 1; while (q != null) { if (p.data == q.data) count++; q = q.next; } // if current counting // is greater than max if (max < count) { res = p.data; max = count; } p = p.next; } return res;} // Push a node to linked list. // Note that this function // changes the head function push(new_data) { var new_node = new Node(); new_node.data = new_data; new_node.next = head_ref; head_ref = new_node;} // Driver code// Start with the empty listhead_ref = null;var str = "skeegforskeeg";var st = str.split('');var i;// this will create a linked// list of character "neveropen"for (i = 0; i < st.length; i++) push(st[i]);document.write(maxChar(head_ref));</script> |
Output:
e
Time complexity: (N*N)
Method 2: (use count array)
Create a count array and count each character frequency return the maximum occurring character.
C++
// C++ program to count the maximum// occurring character in linked list#include <bits/stdc++.h>using namespace std;/* Link list node */struct Node { char data; struct Node *next;};char maxChar(struct Node *head) { struct Node *p = head; int hash[256] = {0}; // Storing element's frequencies // in a hash table. while (p != NULL) { hash[p->data]++; p = p->next; } p = head; int max = -1; char res; // calculating the first maximum element while (p != NULL) { if (max < hash[p->data]) { res = p->data; max = hash[p->data]; } p = p->next; } return res;}/* Push a node to linked list. Note that this function changes the head */void push(struct Node **head_ref, char new_data) { struct Node *new_node = new Node; new_node->data = new_data; new_node->next = (*head_ref); (*head_ref) = new_node;}/* Driver program to test above function*/int main() { struct Node *head = NULL; char str[] = "skeegforskeeg"; for (int i = 0; str[i] != '\0'; i++) push(&head, str[i]); cout << maxChar(head); return 0;} |
Java
// Java program to count the maximum// occurring character in linked listimport java.util.*;class GFG {/* Link list node */static class Node { char data; Node next;};static Node head;static char maxChar(Node head){ Node p = head; int []hash = new int[256]; // Storing element's frequencies // in a hash table. while (p != null) { hash[p.data]++; p = p.next; } p = head; int max = -1; char res = 0; // calculating the first maximum element while (p != null) { if (max < hash[p.data]) { res = p.data; max = hash[p.data]; } p = p.next; } return res;} /* Push a node to linked list. Note thatthis function changes the head */static void push(Node head_ref, char new_data) { Node new_node = new Node(); new_node.data = new_data; new_node.next = head_ref; head_ref = new_node; head = head_ref;}// Driver Codepublic static void main(String[] args){ head = null; char str[] = "skeegforskeeg".toCharArray(); for (int i = 0; i < str.length; i++) { push(head, str[i]); } System.out.println(maxChar(head)); }}// This code is contributed by Rajput-Ji |
Python3
# Python3 program to count the maximum# occurring character in linked list # Link list node class Node: def __init__(self): self.data = '' self.next = Nonedef maxChar(head): p = head hash = [0 for i in range(256)] # Storing element's frequencies # in a hash table. while (p != None): hash[ord(p.data)] += 1 p = p.next p = head max = -1 res = '' # Calculating the first maximum element while (p != None): if (max < hash[ord(p.data)]): res = p.data max = hash[ord(p.data)] p = p.next return res# Push a node to linked list. Note that # this function changes the head def push(head_ref, new_data): new_node = Node() new_node.data = new_data new_node.next = (head_ref) (head_ref) = new_node return head_ref# Driver Codeif __name__=='__main__': head = None str = "skeegforskeeg" for i in range(len(str)): head = push(head, str[i]) print(maxChar(head)) # This code is contributed by pratham76 |
C#
// C# program to count the maximum// occurring character in linked listusing System; public class GFG { /* Link list node */class Node { public char data; public Node next;}; static Node head;static char maxChar(Node head){ Node p = head; int []hash = new int[256]; // Storing element's frequencies // in a hash table. while (p != null) { hash[p.data]++; p = p.next; } p = head; int max = -1; char res= '\x0000'; // calculating the first maximum element while (p != null) { if (max < hash[p.data]) { res = p.data; max = hash[p.data]; } p = p.next; } return res;} /* Push a node to linked list. Note thatthis function changes the head */static void push(Node head_ref, char new_data) { Node new_node = new Node(); new_node.data = new_data; new_node.next = head_ref; head_ref = new_node; head = head_ref;} // Driver Codepublic static void Main(String[] args){ head = null; char []str = "skeegforskeeg".ToCharArray(); for (int i = 0; i < str.Length; i++) { push(head, str[i]); } Console.WriteLine(maxChar(head)); }}// This code is contributed by 29AjayKumar |
Javascript
<script>// JavaScript program to count the maximum// occurring character in linked list// Link list node class Node{ constructor() { this.data = 0; this.next = null; }}var head = null;function maxChar(head) { var p = head; var hash = new Array(256).fill(0); // Storing element's frequencies // in a hash table. while (p != null) { hash[p.data.charCodeAt(0)]++; p = p.next; } p = head; var max = -1; var res = ""; // Calculating the first maximum element while (p != null) { if (max < hash[p.data.charCodeAt(0)]) { res = p.data; max = hash[p.data.charCodeAt(0)]; } p = p.next; } return res;}// Push a node to linked list. Note that// this function changes the head function push(head_ref, new_data){ var new_node = new Node(); new_node.data = new_data; new_node.next = head_ref; head_ref = new_node; head = head_ref;}// Driver Codehead = null;var str = "skeegforskeeg".split("");for(var i = 0; i < str.length; i++) { push(head, str[i]);}document.write(maxChar(head) + "<br>");// This code is contributed by rdtank</script> |
Output:
e
Time complexity: (N)
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!