0
$\begingroup$

On CodingBat.com there's a problem that asks for the length of the longest sequence of repeating characters within a string:

(https://codingbat.com/prob/p179479)


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.

maxBlock("hoopla") → 2

maxBlock("abbCCCddBBBxx") → 3

maxBlock("") → 0


This is the solution I wrote:

public int maxBlock(String str) {

  int max = 0;

  for(int i = 0; i < str.length(); i++)
  {
    char c = str.charAt(i);
    int j = i + 1;
    int possibleMax = 1;

    // iterate through a "block"
    while(j < str.length() && str.charAt(j) == c)
    {
      possibleMax++;
      j++;
    }

    // if the block's length is greater than any found, save it
    if(possibleMax > max)
      max = possibleMax;
  }

  return max;
}

The time complexity is at least O(N) but I'm not sure if the while loop inside makes it O(N^2).

$\endgroup$
2
  • $\begingroup$ Suppose that you will run your program on "aaaaaaa". How many times will j++; be executed? Can you speed up your program? $\endgroup$
    – John L.
    Apr 25, 2019 at 2:42
  • $\begingroup$ @Apass.Jack Yeah, so I added " i = j - 1; " right after the while loop so that after it goes through a sequence of repeated letters, it doesn't try again for each letter, but skips to the end of that sequence. $\endgroup$
    – David
    Apr 25, 2019 at 2:54

1 Answer 1

0
$\begingroup$

The worst-case time complexity is $O(n^{2})$.

Consider the example string "aaaaaaaaaa" — that is, 10 'a's. This happens to be the worse case edge scenario, because j++ has to run for every remaining character in the string, at every position. When i=0, the while loop will run 9 times; when i=1, 8 times; so on until when i=N-1, the loop runs 0 times. Therefore, the total number of times the while loop has to run (over all i) is given by the sum from 0 to N-1, which, with arithmetic series, is $S = \frac{N}{2}(N-1)$. This simplifies to $\frac{N^{2}-N}{2}$; however, when writing time complexity with big-O notation, we ignore constant or slower-growing factors. Therefore, as $N$ grows asymptotically large, the total time complexity reduces to $O(N^{2})$, although in reality it is something closer to $O(\frac{N^{2}}{2})$.

Another way to look at it is that the outer for loop runs exactly $N$ times, and the number of times the inner while loop runs does depend on $N$ (and linearly at that), so the time complexity must be at least greater than $O(n)$.

$\endgroup$
3
  • $\begingroup$ Thank you, that clarifies it. So it's O(N^2) in the worst case. If the string has no sequences of repeating characters, such as "abcdefg" the while loop will run the exact same way for every letter, so would that make the best case O(n)? $\endgroup$
    – David
    Apr 25, 2019 at 3:39
  • $\begingroup$ That's correct, so on average it'd be somewhere in between depending on how long/frequent repeating sequences are. $\endgroup$
    – jasli
    Apr 25, 2019 at 3:41
  • 1
    $\begingroup$ "Another way to look at ... so the time complexity must be at least greater than $𝑂(n)$." Not that it is wrong. However, the logic is not smooth. Had you said "the outer for loop runs exactly $N$ times, so the time complexity must be at least $O(N)$", that would be smooth. $\endgroup$
    – John L.
    Apr 25, 2019 at 4:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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