Message on Whatsapp 8879355057 for DSA(OA + Interview) + Fullstack Dev Training + 1-1 Personalized Mentoring to get 10+LPA Job
0 like 0 dislike
2,023 views
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.
in Algorithms and Problems by Expert (110,440 points) | 2,023 views

4 Answers

1 like 0 dislike
Best answer
#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) . 

by
selected by
0 like 0 dislike

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);
    }
}

 

by
1 like 0 dislike
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);

   }

}
by
0 like 0 dislike
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)
by
0 0
That is not an efficient solution as it takes O(n*n) time.