Index Of Longest Run C#

Question

I am trying to solve this question: Write a function that finds the zero-based index of the longest run in a string. A run is a consecutive sequence of the same character. If there is more than one run with the same length, return the index of the first one.

For example, IndexOfLongestRun("abbcccddddcccbba") should return 6 as the longest run is dddd and it first appears on index 6.

Following what i have done:

private static int IndexOfLongestRun(string str) 
    {
        char[] array1 = str.ToCharArray();
        //Array.Sort(array1);
        Comparer comparer = new Comparer();
        int counter =1;
        int maxCount = 0;
        int idenxOf = 0;

        for (int i =0; i<array1.Length-1 ; i++)
        {
            if (comparer.Compare(array1[i],array1[i+1]) == 0)
            {
                counter++;
            }
            else {
                if(maxCount < counter)
                {
                    maxCount = counter;
                    idenxOf = i - counter + 1;
                }
                counter = 1;
            }
        }
        return idenxOf ;  
    }
}

public class Comparer : IComparer<char>
{
    public int Compare(char firstChar, char nextChar)
    {
        return firstChar.CompareTo(nextChar);
    }
}

The problem is that when i get to the last index for example "abbccaaaaaaaaaa" which is a in this case, and when i=14 (taking this string as example) and when i<array1.Length-1 statment is false, the for loop jumps directrly to return indexOf; and return the wrong index, I am trying to find out how to push the forloop to continue the implementation so idenxOf could be changed to the right index. Any help please?

Answer 1

You could check whether a new best score is achieved for each iteration when current == previous. Minimally slower, but it allows you to write shorter code by omitting an extra check after the loop:

int IndexOfLongestRun(string input)
{
    int bestIndex = 0, bestScore = 0, currIndex = 0;
    for (var i = 0; i < input.Length; ++i)
    {
        if (input[i] == input[currIndex])
        {
            if (bestScore < i - currIndex) 
            {
                bestIndex = currIndex;
                bestScore = i - currIndex;
            }
        }
        else
        {
            currIndex = i;
        }
    }
    return bestIndex;
}

Answer 2

Promote the loop variable i to method scope and repeat the conditional block if (maxCount < counter) { ... } right after the loop exit. Thus, it executes one more time after the loop completes

private static int IndexOfLongestRun(string str)
{
    char[] array1 = str.ToCharArray();
    //Array.Sort(array1);
    Comparer comparer = new Comparer();
    int counter = 1;
    int maxCount = 0;
    int idenxOf = 0;

    int i;
    for (i = 0; i < array1.Length - 1; i++)
    {
        if (comparer.Compare(array1[i], array1[i + 1]) == 0)
        {
            counter++;
        }
        else
        {
            if (maxCount < counter)
            {
                maxCount = counter;
                idenxOf = i - counter + 1;
            }
            counter = 1;
        }
    }
    if (maxCount < counter)
    {
        maxCount = counter;
        idenxOf = i - counter + 1;
    }
    return idenxOf;
}

Answer 3

As usual late, but joining the party. A natural classic algorithm:

static int IndexOfLongestRun(string input)
{
    int longestRunStart = -1, longestRunLength = 0;
    for (int i = 0; i < input.Length; )
    {
        var runValue = input[i];
        int runStart = i;
        while (++i < input.Length && input[i] == runValue) { }
        int runLength = i - runStart;
        if (longestRunLength < runLength)
        {
            longestRunStart = runStart;
            longestRunLength = runLength;
        }
    }
    return longestRunStart;
}

At the end you have both longest run index and length.

Answer 4

  public static int IndexOfLongestRun(string str)
    {
        var longestRunCount = 1;
        var longestRunIndex = 0;
        var isNew = false;

        var dic = new Dictionary<int, int>();

        for (var i = 0; i < str.Length - 1; i++)
        {
            if (str[i] == str[i + 1])
            {
                if (isNew) longestRunIndex = i;
                longestRunCount++;
                isNew = false;
            }
            else
            {
                isNew = true;
                dic.Add(longestRunIndex, longestRunCount);
                longestRunIndex = 0;
                longestRunCount = 1;
            }
        }

        return dic.OrderByDescending(x => x.Value).First().Key;
    }