Find out how long a long sequence is in a string

Question

I recently had this question in an interview, and this is what I came up with. Any feedback?

Find out how long a long sequence is in a string. For example, in the line "abccdeeeeef" the answer would be 5.

static int LongestSeq(string strPass) { int longestSeq = 0; char[] strChars = strPass.ToCharArray(); int numCurrSeq = 1; for (int i = 0; i < strChars.Length - 1; i++) { if (strChars[i] == strChars[i + 1]) { numCurrSeq++; } else { numCurrSeq = 1; } if (longestSeq < numCurrSeq) { longestSeq = numCurrSeq; } } return longestSeq; } 

Answer 1

First comment: you do not need to convert it to a char array. You can index directly to a string.

Second comment: you can easily generalize this to IEnumerable<T> if you want, using foreach and remembering the "current" element.

Third comment: I think the comparison between longestSeq and numCurrSeq would be clearer:

 if (numCurrSeq > longestSeq) 

This is more natural for me, since I usually have a variable part of an expression.

Answer 2

This will return 0 for strings of length 1 (when it should return 1).

Answer 3

Just add 2 pence, here is an alternative using Regex:

 string source = "eeabccdeeeeef"; Regex reg = new Regex(@"(\w)\1+"); MatchCollection matches = reg.Matches(source); int longest = 0; foreach (System.Text.RegularExpressions.Match match in matches) { if (longest < match.Length) longest = match.Length; } 

Due to the fact that I didn’t read the question correctly in the first place when sending my previous answer, I should probably add some actual feedback, given that the question posed by the OP. However, every item I came up with is mentioned by Henrik or Job Skeet, so I just emphasize what John Skeet did; you don't need to convert the string to a char array, you can just index a specific point in the string as follows:

 char letter = someString[4]; 

So everything should work if you replace strChars with strPass .

Answer 4

You can always play the last character, so you don't need to access the array twice in an iteration.

Inside a loop, you can use another loop that iterates as long as the current character matches the last character. After this sublayer, you can put a check if you do not need the current numCurrSeq> longestSeq, check each iteration, but for each subsequence.

Answer 5

I really don’t know what it is (C #?), So justify any minor syntax failures (I don’t know if it is “else if” or “elseif” or “elif” or something else)

 static int LongestSeq(string strPass) { int longestSeq = 1; int curSeqStart = 0; for (int i = 1; i < strPass.Length; i++) { if (strPass[i] != strPass[curSeq]) { curSeqStart = i; } else if (i - curSeqStart + 1 > longestSeq) { longestSeq = i - curSeqStart + 1; } } return longestSeq; } 

Perhaps it would be more efficient to perform

 ... else { len = i - curSeqStart + 1 if ( len > longestSeq ) { longestSeq = len; } } 

or even just

 ... else { longestSeq = max(longestSeq, i - curSeqStart + 1) } 

depending on how good your implementation and max compiler are.

Answer 6

I think this works? I do not write recursive methods at all, I would have completely come up with an answer to the posters.

 public static int recurse(Char last, int seqLength, int currentIndex, int largestSeqLength, string source) { if (currentIndex > source.Length) { return largestSeqLength; } if (source[currentIndex] == last) { seqLength++; if (seqLength > largestSeqLength) { largestSeqLength = seqLength; } } else { seqLength = 1; } return recurse(source[currentIndex], seqLength, currentIndex++, largestSeqLength, source); } 

Answer 7

And another implementation

 public static int LongestSeq<T>(this IEnumerable<T> source) { if (source == null) throw new ArgumentNullException("source"); int result = 0; int currentCount = 0; using (var e = source.GetEnumerator()) { var lhs = default(T); if (e.MoveNext()) { lhs = e.Current; currentCount = 1; result = currentCount; } while (e.MoveNext()) { if (lhs.Equals(e.Current)) { currentCount++; } else { currentCount = 1; } result = Math.Max(currentCount, result); lhs = e.Current; } } return result; } 

Answer 8

A simple (untested) solution would be the following:

 int GetLongestSequence(string input) { char c = 0; int maxSequenceLength = 0; int maxSequenceStart = 0; int curSequenceLength = 0; int length = input.Length; for (int i = 0; i < length; ++i) { if (input[i] == c) { ++curSequenceLength; if (curSequenceLength > maxSequenceLength) { maxSequenceLength = curSequenceLength; maxSequenceStart = i - (curSequenceLength - 1); } } else { curSequenceLength = 1; c = input[i]; } } return maxSequenceStart; } 

Or better structured code (also untested):

 private int GetSequenceLength(string input, int start) { int i = start; char c = input[i]; while (input[i] == c) ++i; // Could be written as `while (input[i++] == c);` but i don't recommend that return (i - start); } public int GetLongestSequence(string input) { int length = input.Length; int maxSequenceLength = 0; int maxSequenceStart = 0; for (int i = 0; i < length; /* no ++i */) { int curSequenceLength = this.GetSequenceLength(input, i); if (curSequenceLength > maxSequenceLength) { maxSequenceLength = curSequenceLength; maxSequenceStart = i; } i += curSequenceLength; } return maxSequenceStart; } 

Answer 9

This extension method finds the longest sequence of identical characters in a string.

  public static int GetLongestSequenceOfSameCharacters(this string sequence) { var data = new List<char>(); for (int i = 0; i < sequence.Length; i++) { if (i > 0 && (sequence[i] == sequence[i - 1])) { data.Add(sequence[i]); } } return data.GroupBy(x => x).Max(x => x.Count()) + 1; } [TestMethod] public void TestMethod1() { // Arrange string sequence = "aabbbbccccce"; // Act int containsSameNumbers = sequence.GetLongestSequenceOfSameCharacters(); // Assert Assert.IsTrue(containsSameNumbers == 5); }