Counting the most frequently appearing character in a string (i.e. the statistical mode)

Question

This is my sample code to find maximum occurrence of characters in string in C#.

How can I make it better?

public static int GetMaximumOccurence(string str)
{
    int _maxcount = 0;

    foreach (char c in str)
    {
        int ix = str.IndexOf(c);
        int count = 0;
        while (ix!=-1)
        {
            StringBuilder _s = new StringBuilder();
            _s.Append(str);
            _s[ix] = ' ';
            str = _s.ToString();

            count++;

            ix = str.IndexOf(c);
        }

        if (count > _maxcount)
        {
            _maxcount = count;
        }
    }

    return _maxcount;
}

Answer 1

I'm worried this is turning into Code Golf, so I'll preface my alternative with some actual review.

There is a pretty big bug in your code, as the following will not terminate:

Console.WriteLine(GetMaximumOccurence(" "));

Can you see why?

The basic structure of your code is good. That is, the part that effectively goes

var maxCount = 0;
foreach (var c in input)
{
    // TODO: Count occurrences of c in input.
    maxCount = Math.Max(count, maxCount);
}

return maxCount;

Now how to we complete that TODO? Using IndexOf like you do seems like a good idea.

var maxCount = 0;
foreach (var c in input)
{
    var count = 0;
    var i = input.IndexOf(c);
    while (i != -1)
    {
        // TODO: Keep counting occurrences of c.
    }

    maxCount = Math.Max(count, maxCount);
}

return maxCount;

Now, string has an overload of IndexOf that takes a starting position. But where do we start searching? We start searching one position after our last found occurrence.

var maxCount = 0;
foreach (var c in input)
{
    var count = 0;
    var i = input.IndexOf(c);
    while (i != -1)
    {
        count++;
        i = input.IndexOf(c, i + 1);
    }

    maxCount = Math.Max(count, maxCount);
}

return maxCount;

If you prefer, this can be written as a for-loop.

var maxCount = 0;
foreach (var c in input)
{
    var count = 0;
    for (var i = input.IndexOf(c); i != -1; i = input.IndexOf(c, i + 1))
    {
        count++;
    }

    maxCount = Math.Max(count, maxCount);
}

return maxCount;

However, this solution is not terribly efficient. For each character in the string, we're iterating over the string again with our calls to IndexOf, so our time complexity is \$O(n^2)\$.

In fact, we've basically just written this:

var maxCount = 0;
foreach (var c in input)
{
    var count = 0;
    foreach (var d in input)
    {
        if (c == d)
        {
            count++;
        }
    }

    maxCount = Math.Max(count, maxCount);
}

return maxCount;

@BlueTrin's answer shows how you can trade space to reduce the time complexity to \$O(n)\$, so I won't go over that here.

All that said, there is an elegant way to express this using LINQ:

return input.Length == 0
    ? 0
    : input.GroupBy(c => c).Max(group => group.Count());

Answer 2

Your code is using a wildcard (' '), wildcards are generally bad as someone else pointed. As a general advice, I would recommend you to avoid writing algorithms based on adding a wildcard when it can be part of the input.

EDIT: this works only if the string does not special UNICODE values as mjolka mentioned, char can be 16-bits in C#.

It depends what you want to optimise, one way to optimise is to use the fact that a char is a value between 0 and 255. Therefore you could initialise directly an array of 255 at 0 values and use it to count each occurrences of each character.

On the pro side, it is much faster because accessing an array is constant in time, there is literally no search or indexing, on the con side it uses a static array of 255 int. Also in C#, if you follow the guidelines of Resharper or StyleCop, they will recommend you to use var when you can and to not use '_' prefixing:

    public static int GetMaximumOccurence(string str)
    {
        var array = new int[255];
        int maxcount = 0;
        foreach (char c in str)
            maxcount = Math.Max(maxcount, ++array[c]);
        return maxcount;
    }

Finally this could be converted in a LINQ expression, which does the same thing:

    public static int GetMaximumOccurence(string str)
    {
        var array = new int[255];
        return str.Select(c => ++array[c]).Concat(new[] {0}).Max();
    }

If you apply dss539 suggestion, it becomes:

    public static int GetMaximumOccurence(string str)
    {
        if (str.Length == 0)
            return 0;
        var array = new int[255];
        return str.Select(c => ++array[c]).Max();
    }

If your string contains UNICODE characters, you will have to revert to a dictionary approach or use dss539 solution or increase the array size to be able to contain 2^16 values to make itwork in every case. Please note that 2^16 int start to be a significant amount of memory for just counting references ...

A Dictionary approach would be:

    public static int GetMaximumOccurence(string str)
    {
        var countPerChar = new Dictionary<char, int>();
        int maxcount = 0;
        foreach (char c in str)
        {
            int newVal;
            if (!countPerChar.TryGet(c, newVal))
                newVal = (countPerChar[c] = 1);
            else
                newVal = (countPerChar[c] += 1);
            maxcount = Math.Max(maxcount, newVal);
        }
        return maxcount;
    }

dss539 suggestion leads to:

    public static int GetMaximumOccurence(string str)
    {
        var countPerChar = new Dictionary<char, int>();
        int maxcount = 0;
        foreach (char c in str)
        {
            int newVal;
            countPerChar.TryGetValue(c, out newVal);        // NewVal is set to 0 if the value is not found
            maxcount = Math.Max(maxcount, (countPerChar[c] = newVal + 1));
        }
        return maxcount;
    }

But I find dss539 answer is superior in the light of knowing that char is 16bit in C#.

Answer 3

Probably less performant than BlueTrin's answer, but worth considering.

Edit: I originally misunderstood the problem to be looking for the character that occurred most frequently (i.e. the "mode" of the data set). Actually, the OP wants to know how many times the mode is repeated in the data set.

static int CountMode<T>(IEnumerable<T> str)
{
    return str.GroupBy(c => c).Select(g => g.Count())
                .OrderBy(freq=>freq).LastOrDefault();
}

Note the similarity to mjolka's LINQ solution. This differs in how the empty string case is handled (since there is no MaxOrDefault()). The ternary version is shorter; however, the LINQ version can work for all IEnumerable<T> without multiple enumeration.