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?

why you used comparer for comparing chars? why not directly compare them? — M.kazem Akhgary, Nov 12 '15 at 14:01
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 http://www.testdome.com/ - I know because I just selected this question for an interview scheduled to take place at my company today. — Lonny B, Nov 12 '15 at 14:01
@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.. — Kob_24, Nov 12 '15 at 14:06
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. — Oguz Ozgul, Nov 12 '15 at 14:10
Add a space to the end of str before reading them into array works for any input. — Martheen, Nov 12 '15 at 14:16
Also you don't need to do `ToCharArray`. `string` has an indexed property to each `char`. — juharr, Nov 12 '15 at 14:24

score 4 · Accepted Answer · answered Nov 12 '15 at 14:26

4

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

answered Nov 12 '15 at 14:26

Kvam

2,148
1
20
32

Bro, i just dont see the benifit of using `++i` instead of ´i++´ because both should work? – Kob_24 Nov 12 '15 at 15:06
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 http://stackoverflow.com/questions/484462/difference-between-i-and-i-in-a-loop for a more detailed explanation of their differences. – Kvam Nov 12 '15 at 15:12

score 2 · Answer 2 · answered Nov 12 '15 at 14:12

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

This could help yeah, but i am trying to find more better solution :) thanks for your effort anyway bro! — Kob_24, Nov 12 '15 at 14:15
Iknow that this could be solved using Linq but Iam not so good at Linq! — Kob_24, Nov 12 '15 at 14:23

score 2 · Answer 3 · answered Nov 13 '15 at 13:06

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.

score 1 · Answer 4 · answered Oct 07 '16 at 03:45

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

this looks nice and simple. – skipper_dev Oct 07 '16 at 03:46 — skipper_dev, Oct 07 '16 at 03:46

score 0 · Answer 5 · answered Nov 12 '15 at 14:21

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;

score 0 · Answer 6 · answered Sep 15 '16 at 15:00

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.

Index Of Longest Run C#

6 Answers6