Index of Longest Run C #

Question

I am trying to solve this question: Write a function that finds the zero index of the longest path in the string. A run is a sequential sequence of the same symbol. If more than one run with the same length is running, return the index of the first.

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

After 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 in this case, and when i=14 (taking this line as an example), and when i<array1.Length-1 statment is false, the for loop translates directly into return indexOf; and returns the wrong index, I'm trying to figure out how to get forloop to continue the implementation so that idenxOf can be changed to the right index. Any help please?

Answer 1

You can check if a new best result was achieved for each iteration with the current == previous one. Minimally slower, but it allows you to write shorter code, omitting additional verification 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

Assist the loop variable in the method area and repeat the conditional block if (maxCount <counter) {...} immediately after the loop exits. Thus, it is executed one more time after the completion of the cycle

 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 join the party. 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; } 

In the end, you have both a long index and a length.

Answer 4

This will return -1 if the string is empty, and you have the flexibility to return the index and 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; 

Answer 5

The accepted answer from Kvam is great for small lines, but as the length approaches 100,000 characters (and maybe this is not required), its effectiveness is increased.

 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 with large strings. Perhaps there are other optimizations.

Answer 6

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