How to find the most occurring character in a string in O(n) ?

Question

Constraints :

1)String consists only of lowercase English letters .

2)1<=N<=1000000 , where 'N' is the length of the string .

Giving explanation is mandatory , giving code depends on your choice . Also add your name at the bottom of answer so you get the due credits. Direct libraries in python are not allowed to be used as they skip the lagorithm parts sometimes.

Answer 1

#include<bits/stdc++.h>
using namespace std;
int main()
{
    string s;
    vector<long long> a(26);
    cin>>s;
    for(long long i=0;i<s.length();i++)
    {
        int x = (int)(s[i]-'a');
        a[x]++;
        
    }
    long long mx=-1;
    char c;
    for(long long i=0;i<26;i++)
    {
        if(mx<a[i])
        {
            mx=a[i];
            c='a' +i;
        }
    
    }
    cout<<c;
    return 0;
}

Time Complexity : O(n) 

There are 2 more approaches : 

1) We can sort the string, keep a variable of count and whenever there is a change in character just compare the count with max, Time-O(nlogn)

2) Use a hashmap intead of an array to store the frequency, the key in that case will be a character and value will be an integer storing the frequency of that character , time - O(n) . 

Answer 2

Approach  : 

1. Created an integer array of 26 for storing a count of character occurred in the string  there are 26 alphabet I had created an array of 26
2. After that, just iterated over a string and incremented an count of corresponding index value 
3. Iterated over an int array in order to find a character occur and max count

Complexity :

• Time complexity: O(n)
• Space Complexity : O(26) -------- Constant space complexity

Code : Java 8 code

 

package com.desi.qna;

import java.util.Arrays;

public class ShortestLengthString {
    public static void main(String[] args) {
        int arr[] = new int[26];
        String s= "Javvva";
        s = s.toLowerCase();
        Arrays.fill(arr, 0);
//        System.out.println((int)s.charAt(0)+" "+s.charAt(0));

        for(int i=0;i<s.length();i++) {
            if(arr[(int)s.charAt(i)-(int)'a'] > 0) {
                arr[(int)s.charAt(i)-(int)'a']++;
            }else {
                arr[(int)s.charAt(i)-(int)'a']=1;
            }
        }
        int max = Integer.MIN_VALUE;
        int index=-1;
        for(int i=0;i<26;i++){
            if(max < arr[i]) {
                max = arr[i];
                index = i;
            }
        }
        System.out.println("character occur = "+(char)((int)'a'+index)+" "+" maxcount = "+max);
    }
}

 

Answer 3

C# code : 
//Time Complexity : O(N) 


using System;

using System.Linq;

class Program

{

   static void Main()

   {

    string s = Console.ReadLine();

    int count = 0;

    char high=' ';

    for (int i = 0; i < s.Length; i++)

    {

       int j = s.where(t => t.Equals(s[i])).Count();          

      if (j > count)

       {

      count = j;

      high = s[i];

       }

    }

  Console.Writeline (high);

   }

}

Answer 4

s=input()
mc=0
for i in range(len(s)):
    c=0
    for j in range(len(s)):
        if s[i]==s[j]:
            c+=1
    if mc<c:
        mc=c
        z=s[i]
print(z)

Comments

That is not an efficient solution as it takes O(n*n) time.