Find the longest sequence of identical characters in a string

Question

This code should output the longest run at which the character in the string has consecutive runs. Although the problem is that it outputs: 8 (there should be 5 instead). I just wanted to ask what is the problem with this code.

public class Sample { public static void main(String[] args) { String setofletters = "aaakkcccccczz"; /* 15 */ int output = runLongestIndex(setofletters); System.out.println("Longest run that first appeared in index:" + output); } public static int runLongestIndex(String setofletters) { int ctr = 0; int ctrstor = 0; int ii = 0; int output = 0; // loops until the last character in the string for (int i = 0; i < setofletters.length() - 1; i++) { // checks if the letter is the same to the next if (setofletters.charAt(i) == setofletters.charAt(i++)) { ctr++; ii = i++; // loops until the letter in the index is no longer equal while (setofletters.charAt(i) == setofletters.charAt(ii)) { ii++; ctr++; } if (ctr > ctrstor) { output = i; } // storing purposes ctrstor = ctr; } // resets the counter ctr = 0; } return output; } } 

Answer 1

UPDATE Sorry, I misunderstood your question, you need to make the following changes to your code in order for it to work. (comment lines)

  public static int runLongestIndex(String setofletters){ int ctr = 1; // every character is repeated at least once, so you should initialize it to 1, not 0 int ctrstor = 0; int ii = 0; int output = 0; for (int i = 0; i < setofletters.length() - 1; i++) { if (i < setofletters.length() - 1 && setofletters.charAt(i) == setofletters.charAt(i+1)) { // i++ is not same as i+1 ctr++; ii = i+1; // i++ is not same as i+1 while (setofletters.charAt(i) == setofletters.charAt(ii)) { ii++; ctr++; } if (ctr > ctrstor) { output = i; } ctrstor = ctr; } ctr = 1; // for the same reason I mentioned above } return output; } 

EDIT : the easiest way to write code:

 public static int runLongestIndex(String setofletters){ int ctr = 1; int output = 0; int j=0; for(int i=0; i<setofletters.length()-1;i++){ j=i; while(i <setofletters.length()-1 && setofletters.charAt(i)==setofletters.charAt(i+1)){ i++; ctr++; } if(ctr>output){ output=j; } ctr = 1; } return output; } 

Why are you assigning i for output? You must assign ctr output .

change

  if(ctr>ctrstor){ output=i; } 

to

  if(ctr>ctrstor){ output=ctr; } 

and I think you should change

  if(setofletters.charAt(i)==setofletters.charAt(i++)) 

to

  if(i<setofletters.length()-1 && setofletters.charAt(i)==setofletters.charAt(i+1)){ 

and you have to do intialize ctr to 1 , but not 0 , because each character is repeated at least once.

Answer 2

I will give you a Scala implementation for this problem.

Here it is an automatic test (in BDD style with ScalaTest)

 import org.scalatest._ class RichStringSpec extends FlatSpec with MustMatchers { "A rich string" should "find the longest run of consecutive characters" in { import Example._ "abceedd".longestRun mustBe Set("ee", "dd") "aeebceeedd".longestRun mustBe Set("eee") "aaaaaaa".longestRun mustBe Set("aaaaaaa") "abcdefgh".longestRun mustBe empty } } 

The following is an imperative style implementation with nested loops and mutable variables that you usually choose in Java or C ++:

 object Example { implicit class RichString(string: String) { def longestRun: Set[String] = { val chunks = mutable.Set.empty[String] val ilen = string.length var gmax = 0 for ((ch, curr) <- string.zipWithIndex) { val chunk = mutable.ListBuffer(ch) var next = curr + 1 while (next < ilen && string(next) == ch) { chunk += string(next) next = next + 1 } gmax = chunk.length max gmax if (gmax > 1) chunks += chunk.mkString } chunks.toSet.filter( _.length == gmax ) } } } 

The implementation of the functional style is given below, so there are no variables, no loops, but tail recursion with result storages and pattern matching to compare each character with the next (crazy!)?

 object Example { implicit class RichString(string: String) { def longestRun: Set[String] = { def recurse(chars: String, chunk: mutable.ListBuffer[Char], chunks: mutable.Set[String]): Set[String] = { chars.toList match { case List(x, y, _*) if (x == y) => recurse( chars.tail, if (chunk.isEmpty) chunk ++= List(x, y) else chunk += y, chunks ) case Nil => // terminate recursion chunks.toSet case _ => // x != y recurse( chars.tail, chunk = mutable.ListBuffer(), chunks += chunk.mkString ) } } val chunks = recurse(string, mutable.ListBuffer(), mutable.Set.empty[String]) val max = chunks.map(_.length).max if (max > 0) chunks.filter( _.length == max ) else Set() } } } 

For example, for a given string "aeebceeedd" both implementations described above will contain the following set of pieces (duplicate characters)

 Set("ee", "eee", "dd") 

and they will filter those pieces that have the maximum length (the result is "eee" ).

Answer 3

This code should work for any length of string sequence.

 public class LongestStringSequqnce { static String myString = "aaaabbbbcccchhhhiiiiibbbbbbbbbccccccc"; static int largestSequence = 0; static char longestChar = '\0'; public static void main(String args[]) { int currentSequence = 1; char current = '\0'; char next = '\0'; for (int i = 0; i < myString.length() - 1; i++) { current = myString.charAt(i); next = myString.charAt(i + 1); // If character are in sequence , increase the counter if (current == next) { currentSequence += 1; } else { if (currentSequence > largestSequence) { // When sequence is // completed, check if // it is longest largestSequence = currentSequence; longestChar = current; } currentSequence = 1; // re-initialize counter } } if (currentSequence > largestSequence) { // Check if last string // sequence is longest largestSequence = currentSequence; longestChar = current; } System.out.println("Longest character sequence is of character " + longestChar + " and is " + largestSequence + " long"); } } 

Source: http://www.5balloons.info/program-java-code-to-find-longest-character-sequence-in-a-random-string/

Answer 4

  if(ctr>ctrstor){ output=i; } //storing purposes ctrstor=ctr; 

This seems like a problem. Therefore, if you find 8 consecutive characters, it will set the output to 8 and continue. Next time it will find 3 consecutive characters, therefore it does not set the output, but sets ctrstor. Next time through it there will be 4 consecutive characters, and this will set the output to 4

Answer 5

There are several pitfalls in the code in which your logic was felt:

• The code incorrectly assumes that there is always the next character to compare the current one.
  This is not true for a string of type "a" or the last character in any string.

• The code does not store the maximum number of characters, but only the maximum index ( i ).
  MaxCount is needed to compare the next character sequence size.

• Loop for and loop while repeat the same subset of characters.

• Also, the style of a variable name makes code difficult to understand.

After the correction above

 public static int runLongestIndex(String setofletters) { int maxCount = 0; int maxIndex = 0; // loops each character in the string for (int i = 0; i < setofletters.length() - 1; ) { // new char sequence starts here char currChar = setofletters.charAt(i); int count = 1; int index = i; while ( (index < setofletters.length() - 1) && (currChar == setofletters.charAt(++index)) ) { count++; } if (count > maxCount) { maxIndex = i; maxCount = count; } i = index; } return maxIndex; } 

See Java DEMO

Answer 6

I think you do not need an inner loop:

 public static int runLongestIndex(String setofletters) { if (setofletters == null || setofletters.isEmpty()) { return -1; } int cnt = 1; char prevC = setofletters.charAt(0); int maxCnt = 1; //char maxC = prevC; int maxRunIdx = 0; int curRunIdx = 0; for (int i = 1; i < setofletters.length(); i++){ final char c = setofletters.charAt(i); if (prevC == c) { cnt++; } else { if (cnt > maxCnt) { maxCnt = cnt; //maxC = prevC; maxRunIdx = curRunIdx; } cnt = 1; curRunIdx = i; } prevC = c; } if (setofletters.charAt(setofletters.length() - 1) == prevC) { if (cnt > maxCnt) { //maxC = prevC; maxCnt = cnt; maxRunIdx = curRunIdx; } } return maxRunIdx; } 

and this code: System.out.println (runLongestIndex ("aaakkcccccczzzz")); gives you 5

Answer 7

This is how my colleague understands that you need to write readable code to solve this problem, even if it works :)

  public static int count (String str) { int i = 0; while(i < str.length()-1 && str.charAt(i)==str.charAt(i+1)) i ++; return ++i; } public static int getLongestIndex(String str){ int output = 0; for(int i=0, cnt = 1, counter = 0 ; i<str.length() - 1;i += cnt, cnt = count(str.substring(i)), output = (counter = (cnt > counter ? cnt : counter)) == cnt ? i : output); return output; } 

Answer 8

int indexOfLongestRun (String str) {

  char[] ar = str.toCharArray(); int longestRun = 0; int lastLongestRun = 0; int index = 0; for(int i = ar.length-1; i>0; i--){ if(ar[i] == ar[i-1]){ longestRun++; }else{ if(longestRun > lastLongestRun){ lastLongestRun = longestRun; longestRun = 0; index = i; } } } return index;