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?

Conservatoire

yes at the close bracket of the for loop – Conservatoire

ohh sorry i mean indexOf – Conservatoire

why you used comparer for comparing chars? why not directly compare them? – Loveinamist

This is an interview question being asked of you from a potential employer. Should we really be helping you with this? This question was taken from testdome.com - I know because I just selected this question for an interview scheduled to take place at my company today. – Nunez

@M.kazemAkhgary I know that but i just wanted to test it – Conservatoire

@LonnyB no one asked it to me i am just trying to work on my skills before i make the test for a job interview.. – Conservatoire

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. – Earlap

Add a space to the end of str before reading them into array works for any input. – Splash

Also you don't need to do ToCharArray. string has an indexed property to each char. – Kelseykelsi

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

Biliary

Bro, i just dont see the benifit of using ++i instead of ´i++´ because both should work? – Conservatoire

In single statements both will work just fine. I personally prefer ++i over i++, and I try not to use it at all in ambiguous situations. Take a look at #484962 for a more detailed explanation of their differences. – Biliary

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

Earlap

This could help yeah, but i am trying to find more better solution :) thanks for your effort anyway bro! – Conservatoire

You are looking for a better one. Ok. – Earlap

Iknow that this could be solved using Linq but Iam not so good at Linq! – Conservatoire

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.

Halutz

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

Barbrabarbuda

this looks nice and simple. – Barbrabarbuda

Answer 5

This will return -1 if the string is empty and you have the flexibility of returning the index and the count depending on your specification.

        string myStr = "aaaabbbbccccccccccccdeeeeeeeee";

        var longestIndexStart = -1;
        var longestCount = 0;
        var currentCount = 1;
        var currentIndexStart = 0;

        for (var idx = 1; idx < myStr.Length; idx++)
        {
            if (myStr[idx] == myStr[currentIndexStart])
                currentCount++;
            else
            {
                if (currentCount > longestCount)
                {
                    longestIndexStart = currentIndexStart;
                    longestCount = currentCount;
                }

                currentIndexStart = idx;
                currentCount = 1;
            }
        }

        return longestIndexStart;

Delaunay

Answer 6

The accepted answer from Kvam works great for small strings, but as the length approaches 100,000 characters (and perhaps this isn't needed), its efficiency wains.

public static int IndexOfLongestRun(string str)
    {
        Dictionary<string, int> letterCount = new Dictionary<string, int>();

        for (int i = 0; i < str.Length; i++)
        {
            string c = str.Substring(i, 1);                       

            if (letterCount.ContainsKey(c))

                letterCount[c]++;
            else

                letterCount.Add(c, 1);
        }

        return letterCount.Values.Max();
    }

This solution is twice as fast as Kvam's with large strings. There are, perhaps, other optimizations.

Arioso