LeetCode 434: Number of Segments in a String

Problem Restatement

We are given a string s.

A segment is a contiguous sequence of non-space characters.

We need to count how many segments appear in the string.

For example:

s = "Hello, my name is John"

contains these segments:

"Hello,"
"my"
"name"
"is"
"John"

So the answer is:

5

The official problem defines a segment as a contiguous sequence of non-space characters. The string may contain leading spaces, trailing spaces, or multiple spaces between words. (leetcode.com)

Input and Output

Example function shape:

def countSegments(s: str) -> int:
    ...

Examples

Example 1:

s = "Hello, my name is John"

Segments:

Hello,
my
name
is
John

Answer:

5

Example 2:

s = "Hello"

There is only one segment:

1

Example 3:

s = "   Hello   world   "

The extra spaces do not create empty segments.

Only these count:

Hello
world

Answer:

2

Example 4:

s = ""

No segments exist.

Answer:

0

First Thought: Split the String

A direct idea is:

s.split()

Python automatically removes repeated spaces.

For example:

"   Hello   world   ".split()

becomes:

["Hello", "world"]

So we could simply return:

len(s.split())

This works.

However, the problem becomes more interesting if we solve it manually using character scanning.

Key Insight

A new segment starts when:

1. The current character is not a space.
2. Either:
   • it is the first character, or
   • the previous character is a space.

So we only need to count transitions like:

space -> non-space

For example:

"   Hello   world"
     ^

The H starts a new segment because it follows a space.

Later:

"   Hello   world"
             ^

The w also starts a new segment.

This lets us solve the problem in one pass.

Algorithm

Initialize:

count = 0

Scan the string from left to right.

For each character s[i]:

If:

s[i] != ' '

and:

i == 0 or s[i - 1] == ' '

then we found the start of a new segment.

Increase:

count += 1

After scanning the whole string, return count.

Correctness

A segment is defined as a maximal contiguous sequence of non-space characters.

Every segment has exactly one starting position:

The algorithm counts exactly these positions.

Suppose a segment starts at index i.

Then:

s[i] != ' '

and either:

i == 0

or:

s[i - 1] == ' '

So the algorithm increases the count once for that segment.

Now consider any counted position.

The algorithm only counts when a non-space character begins after a space or at the beginning of the string. Therefore, the counted position must be the first character of a segment.

Since every segment is counted exactly once and no non-segment positions are counted, the returned value equals the number of segments.

Complexity

Here, n is the length of the string.

Implementation

class Solution:
    def countSegments(self, s: str) -> int:
        count = 0

        for i in range(len(s)):
            if s[i] != ' ' and (i == 0 or s[i - 1] == ' '):
                count += 1

        return count

Code Explanation

We begin with:

count = 0

This stores the number of detected segments.

We scan every character:

for i in range(len(s)):

The first condition:

s[i] != ' '

ensures the current character belongs to a segment.

The second condition:

i == 0 or s[i - 1] == ' '

checks whether this character begins a new segment.

If both conditions hold, we increment the answer:

count += 1

Finally, we return the total number of segment starts.

Testing

def run_tests():
    s = Solution()

    assert s.countSegments("Hello, my name is John") == 5

    assert s.countSegments("Hello") == 1

    assert s.countSegments("   Hello   world   ") == 2

    assert s.countSegments("") == 0

    assert s.countSegments("      ") == 0

    assert s.countSegments("a b c") == 3

    assert s.countSegments("   a") == 1

    assert s.countSegments("a   ") == 1

    print("all tests passed")

run_tests()

Test meaning: