Approach #1 Using Language Builtins [Accepted]

Intuition

In a situation where raw efficiency is less important than code legibility,\nit is likely better to use language-idiomatic builtin functions to solve this\nproblem.

Algorithm

There are a few corner cases that you can get snagged on in this problem, at\nleast in Java. First, one or more leading spaces will cause split to deduce\nan erroneous "" token at the beginning of the string, so we use the builtin\ntrim method to remove leading and trailing spaces. Then, if the resulting\nstring is the empty string, then we can simply output 0. This is necessary due\nto the following behavior of the split method:

String[] tokens = "".split("\\\\s++");\ntokens.length; // 1\ntokens[0]; // ""\n

If we reach the final return statement, we split the trimmed string on\nsequences of one or more whitespace characters (split can take a regular\nexpression) and return the length of the resulting array.

The Python solution is trivially short because Python\'s split has a lot of\ndefault behavior that makes it perfect for this sort of problem. Notably, it\nreturns an empty list when splitting an empty string, it splits on\nwhitespace by default, and it implicitly trims (strips, in Python lingo)\nthe string beforehand.

Complexity Analysis

\n
• \n

  Time complexity : $$O(n)$$ \n

  \n

  All builtin language functionality used here (in both the Java and Python\nexamples) runs in either $$O(n)$$ or $$O(1)$$ time, so the entire algorithm\nruns in linear time.

  \n
\n
• \n

  Space complexity : $$O(n)$$ \n

  \n

  split (in both languages) returns an array/list of $$O(n)$$ length, so\nthe algorithm uses linear additional space.

  \n
\n

Approach #2 In-place [Accepted]

Intuition

If we cannot afford to allocate linear additional space, a fairly simple\nalgorithm can deduce the number of segments in linear time and constant\nspace.

Algorithm

To count the number of segments, it is equivalent to count the number of\nstring indices at which a segment begins. Therefore, by formally defining the\ncharacteristics of such an index, we can simply iterate over the string and\ntest each index in turn. Such a definition is as follows: a string index\nbegins a segment if it is preceded by whitespace (or is the first index) and\nis not whitespace itself, which can be checked in constant time. Finally, we\nsimply return the number of indices for which the condition is satisfied.

Complexity Analysis

\n
• \n

  Time complexity : $$O(n)$$ \n

  \n

  We do a constant time check for each of the string\'s $$n$$ indices, so the\nruntime is overall linear.

  \n
\n
• \n

  Space complexity : $$O(1)$$ \n

  \n

  There are only a few integers allocated, so the memory footprint is\nconstant.

  \n
\n

Analysis written by: @emptyset