4
\$\begingroup\$

I have been going through some CodingBat exercises and I came across this problem. "Given a string, return the length of the largest "block" in the string. A block is a run of adjacent chars that are the same."

Required output:

maxBlock("hoopla") → 2
maxBlock("abbCCCddBBBxx") → 3
maxBlock("") → 0

My code seems to pass all the tests except for the last "other test". Can someone please review my code and tell me where exactly I could have gone wrong?

 public int maxBlock(String str) {
      int charBlock = 0;
      int holder = 1;
      if(str.length() == 0){ //If string is empty return 0
         charBlock = 0;
      } else if(str.length() == 1){ //If string contains only a single char return 1
         charBlock = 1;
      } else {
          for(int i=0; i < str.length()-1; i++){   //loop through each char value
              if((str.length() == 2) && (str.charAt(i) != str.charAt(i+1))){ 
                  charBlock =1; //return 1 if the length of the string is 2 and non of the two chars match
              }   
              else if((str.length() == 3) && (str.charAt(i) != str.charAt(i+1))){
                 charBlock = 1; //return 1 if the length of the string is 3 and non of the three chars match
              } 
              else if (str.charAt(i) == str.charAt(i+1)){
                 holder = holder + 1; 
                   if(holder > charBlock){
                     charBlock = holder; //update the value of charBlock if a holder is larger current value
                     }
             } else holder = 1; 
          }
      }
      return charBlock;
    }

Example test cases:

Expected    Run     
maxBlock("hoopla") → 2  2   OK      
maxBlock("abbCCCddBBBxx") → 3   3   OK      
maxBlock("") → 0    0   OK      
maxBlock("xyz") → 1 1   OK      
maxBlock("xxyz") → 2    2   OK      
maxBlock("xyzz") → 2    2   OK      
maxBlock("abbbcbbbxbbbx") → 3   3   OK      
maxBlock("XXBBBbbxx") → 3   3   OK      
maxBlock("XXBBBBbbxx") → 4  4   OK      
maxBlock("XXBBBbbxxXXXX") → 4   4   OK      
maxBlock("XX2222BBBbbXX2222") → 4   4   OK      
other tests                             X
\$\endgroup\$
  • 2
    \$\begingroup\$ In general, questions containing broken code are off-topic for Code Review. However, I see that it passes basic tests, and questions about correctness in unanticipated cases are OK. Therefore, I'm reopening this question. \$\endgroup\$ – 200_success Dec 9 '14 at 20:45
7
\$\begingroup\$

The missed edge case

The test case you're missing is longer text with non-repeating letters, for example: abcdefghijkl. And it's easy to fix that: just add these lines before the return statement:

    if (holder > charBlock) {
        charBlock = holder;
    }

The biggest clue for figuring out this problem was around these lines:

if((str.length() == 2) && (str.charAt(i) != str.charAt(i+1))){
    charBlock =1; //return 1 if the length of the string is 2 and non of the two chars match
}
else if((str.length() == 3) && (str.charAt(i) != str.charAt(i+1))){
    charBlock = 1; //return 1 if the length of the string is 3 and non of the three chars match
}
else if (str.charAt(i) == str.charAt(i+1)){

That is, the special treatment for length 2 and 3. There doesn't seem to be a logical reason to treat these cases any special, and you could have quessed that this might break for longer strings. And as it turns out, these conditions are completely unnecessary: you can safely remove them, and the code will still pass the tests.

Code review

About this piece:

  int charBlock = 0;
  int holder = 1;
  if(str.length() == 0){ //If string is empty return 0
     charBlock = 0;
  } else if(str.length() == 1){ //If string contains only a single char return 1
     charBlock = 1;
  } else {
     // ...
  }
  return charBlock;

Two things:

  • It's good to use early returns to reduce the indent level and make the code more readable
  • It's good to limit variables to the smallest scope possible

These two ideas go hand in hand in this example. Consider this alternative:

    if (str.length() == 0) {
        return 0;
    }
    if (str.length() == 1) {
        return 1;
    }
    int charBlock = 0;
    int holder = 1;
    // ...
    return charBlock;

The guard statements don't need the charBlock or holder variable, they can simply return, and now those variables are declared where they are really needed.

When checking if a string is empty, use str.isEmpty() instead of checking on the length.

And in this program, you don't actually need the str.length() == 1 check, if you omit it the program will still work and pass the tests.

But the single biggest problem with this code, in my opinion, is the naming of the variables charBlock and holder. I would name them longest and length, respectively.

Putting the above suggestions together, the implementation becomes this:

    if (str.isEmpty()) {
        return 0;
    }
    int longest = 0;
    int length = 1;
    for (int i = 0; i < str.length() - 1; i++) {
        if (str.charAt(i) == str.charAt(i + 1)) {
            ++length;
            if (length > longest) {
                longest = length;
            }
        } else {
            length = 1;
        }
    }
    if (length > longest) {
        longest = length;
    }
    return longest;

Almost. There is one more important improvement to do: why update the longest length while still counting the same letters? It would be more efficient to move that piece of code to the else block, like this:

        if (str.charAt(i) == str.charAt(i + 1)) {
            ++length;
        } else {
            if (length > longest) {
                longest = length;
            }
            length = 1;
        }

Unit testing

When refactoring non-trivial code like this, it's good to have unit tests to make it easy to re-validate everything, for example:

@Test
public void test_hoopla() {
    assertEquals(2, maxBlock("hoopla"));
}

@Test
public void test_abbCCCddBBBxx() {
    assertEquals(3, maxBlock("abbCCCddBBBxx"));
}

@Test
public void test_empty() {
    assertEquals(0, maxBlock(""));
}

@Test
public void test_xyz() {
    assertEquals(1, maxBlock("xyz"));
}

@Test
public void test_xxyz() {
    assertEquals(2, maxBlock("xxyz"));
}

@Test
public void test_longer_nonrepeating_sequence() {
    assertEquals(1, maxBlock("abcdefghijkl"));
}

Especially when the contest provides the cases you should pass. Heck, it's good to write unit tests always.

\$\endgroup\$
  • 1
    \$\begingroup\$ I think the biggest issue here was the special validation for length 2 and 3 strings, I think it's so important that you could make that part in bold! Nice review. \$\endgroup\$ – Bruno Costa Dec 9 '14 at 20:54
  • \$\begingroup\$ @BrunoCosta Thanks! I was about halfway, still writing. Check again now! \$\endgroup\$ – janos Dec 9 '14 at 21:06
0
\$\begingroup\$
  • Avoid multiple if-else blocks. Simplicity rules.
  • Pre-calculate values to avoid multiple points of extraction. str.charAt(i)
  • Length checks for 0,1,>1 should be implicitly handled in the loop itself.

    public static int maxLen(String input){
        // Avoid NPEs
        if(input==null){
            return 0;
        }
        int maxLen = 0;
        int tempLen = 0;
        char prevChar = 0;
        for(int i=0;i<input.length();i++){
            final char c =input.charAt(i);
            if(c == prevChar){
                tempLen++;
            }else{
                maxLen = (tempLen>maxLen)?tempLen:maxLen;
                prevChar = c;
                tempLen = 1;
            }
        }
        maxLen = (tempLen>maxLen)?tempLen:maxLen;
        return maxLen;
    }
    
  • Add test cases to get clarity in the implementation null -> 0 "" -> 0 "a" -> 1 "aa" -> 2 "abcddd" -> 3 "abcd" -> 1

\$\endgroup\$
0
\$\begingroup\$

Having lots of conditionals makes code difficult to read, which is reflected in the fact that you've had to put comments throughout the code to remind yourself how it works!

How about this...

public int maxBlock(String s) {
    if (s == null) {
        return 0;
    }
    char previousChar = 0;
    int longestRun = 0;
    int currentRun = 0;
    for (char currentChar : s.toCharArray()) {
        if (currentChar == previousChar) {
            currentRun++;
        } else {
            longestRun = Math.max(currentRun, longestRun);
            currentRun = 1;
            previousChar = currentChar;
        }
    }
    return Math.max(currentRun, longestRun);
}

To add one more thing to janos's review suggestions, one thing I noticed is that many of your comments are saying essentially the same thing as the code. I'd suggest leaving them out. Developers can read code and trust it more than comments, which often get out of sync with the code.

\$\endgroup\$
  • \$\begingroup\$ Check for "aa". \$\endgroup\$ – thepace Dec 10 '14 at 10:39
0
\$\begingroup\$

Here is the easy to understand and compact code for finding longest sequence of chars in a given string.

public static int longestSequence(String str) {


    if(str.length() == 0) return 0;


    int max=0;
    for(int i=0;i<str.length();i++){
        int count=0;
        for(int j=i;j<str.length();j++){
            if(str.charAt(i) == str.charAt(j)){
                count ++;
            }else{
                break;
            }

        }
        if(count >max){
            max=count;
        }

    }

    return max;
}

output :longestSequence(XX2222BBBbbXX2222) -> 4

\$\endgroup\$
  • 1
    \$\begingroup\$ Hi. Welcome to Code Review! While code suggestions are welcome, we usually prefer more review in answers. Why is this better than the original code? \$\endgroup\$ – mdfst13 Apr 5 '16 at 18:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.