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$
  • $\begingroup$ Suppose that you will run your program on "aaaaaaa". How many times will j++; be executed? Can you speed up your program? $\endgroup$ – Apass.Jack Apr 25 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 at 2:54
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$
  • $\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 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 at 3:41
  • $\begingroup$ That makes sense, thanks! $\endgroup$ – David Apr 25 at 4:24
  • 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$ – Apass.Jack Apr 25 at 4:48

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.