Finding most frequent char for a given word

Question

I want to use System.Linq for writing a method that returns the first, most frequent character in a string. eg: "AABABBC" => 'A'. If two letters occur the same, the first one that appears in the string should be returned.

The sample below should work. However, I'm trying to find a more efficient solution, which doesn't imply sorting the characters first. I was thinking of using Enumerable.Aggregate() for counting the repetitions while also iterating through the word. Not sure how to to that, though... Any ideas? Thanks :)

    public static char MostAparitionsChar(string word)
    {
       return word.GroupBy(x => x)
            .OrderByDescending(x => x.Count())
            .Select(g => g.Key)
            .First();  
    }

What is *more efficient* in your case, please? Should it be faster or consume less memory? — Dmitry Bychenko, Oct 08 '19 at 08:49
Faster :) Instead of iterating 3 times through my string, I wanted to only iterate once — Balada Rock, Oct 08 '19 at 08:53
What makes you think that your code iterates through your string three times? — canton7, Oct 08 '19 at 08:56
Question: What if all letter have the same number of occurrence? "abcd" — xdtTransform, Oct 08 '19 at 08:59
True enough, but then, apllying OrderByDescending and Select reiterate the projection results, which is why I don't find it very efficient. It looks to me that I should be able to directly count the repetitions, if I could somehow write my Linq expression as: word.Aggregate(0, (Function()); — Balada Rock, Oct 08 '19 at 09:00

score 0 · Accepted Answer · answered Oct 08 '19 at 09:02

I don't know the exact implementation of OrderByDescending, but I assume it is not faster than O(n*log n). But finding a maximum value should only be O(n). Hence you can save some time if you don't sort, but only look for the maximum:

public static char MostAparitionsChar(string word)
 {
 char result = ' ';
 int max = int.MinValue;
 foreach(var grouping in word.GroupBy(x => x))
  {
  int count = grouping.Count();
  if(count > max)
   {
   max = count;
   result = grouping.Key;
  }
 }
 return result;
}

Note that this only applies to .NET Framework. .NET Core already has an optimization for `OrderBy(...).First()` — canton7, Oct 08 '19 at 09:52

Finding most frequent char for a given word

1 Answers1