LeetCode 434 - Number of Segments in a String

The problem asks us to count how many separate word-like groups exist inside a string. In this problem, a "segment" is defined as a continuous sequence of characters that are not spaces.

leetcodeeasystring

LeetCode Problem 434

Difficulty: 🟢 Easy
Topics: String

Solution

Problem Understanding

The problem asks us to count how many separate word-like groups exist inside a string. In this problem, a "segment" is defined as a continuous sequence of characters that are not spaces. Every time we encounter a block of non-space characters separated by spaces, that block counts as one segment.

For example, in the string "Hello, my name is John", there are five separate groups of non-space characters:

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

Therefore, the answer is 5.

The input is a single string s, and the output is an integer representing how many segments appear in that string. The string may contain uppercase letters, lowercase letters, digits, punctuation symbols, and spaces. Importantly, the only whitespace character allowed is the regular space character ' '.

The constraints are very small, since the maximum length of the string is only 300 characters. This means even less efficient approaches would still run comfortably within limits. However, the goal is still to design a clean and optimal solution.

Several edge cases are important to consider carefully. The string could be empty, which should return 0. The string could contain only spaces, which should also return 0. Multiple consecutive spaces may appear between words, so we cannot simply count spaces and assume each one separates segments. Leading and trailing spaces must also be handled correctly, because they do not create additional segments.

A correct solution must count only transitions into a non-space sequence.

Approaches

Brute Force Approach

A straightforward approach is to split the string using spaces and count how many resulting pieces are non-empty.

For example:

"Hello, my name".split(" ")

produces:

["Hello,", "my", "name"]

However, consecutive spaces create empty strings:

"Hello   world".split(" ")

produces:

["Hello", "", "", "world"]

We would then need to iterate through the resulting array and count only non-empty strings.

This approach works because every valid segment becomes one non-empty substring after splitting. Empty strings appear only because of repeated spaces.

Although this solution is acceptable for the given constraints, it uses extra memory to store all substrings created during the split operation.

Optimal Approach

The better approach is to scan the string once and count the beginning of each segment directly.

The key observation is that a new segment starts whenever:

  • the current character is not a space, and
  • either it is the first character in the string, or the previous character is a space

This allows us to identify exactly where each segment begins without splitting the string or storing intermediate substrings.

For example, in:

"Hello, my name"

the segment starts occur at:

  • 'H'
  • 'm'
  • 'n'

Each of these characters either appears at index 0 or immediately follows a space.

This approach is optimal because it processes the string in a single pass and uses constant extra memory.

Approach Time Complexity Space Complexity Notes
Brute Force O(n) O(n) Split the string and count non-empty parts
Optimal O(n) O(1) Count segment starts during one traversal

Algorithm Walkthrough

Optimal Algorithm

  1. Initialize a counter variable count to 0.

This variable will store the number of segments found in the string. 2. Iterate through the string character by character using an index.

We need the index because determining whether a segment starts depends on the previous character. 3. For each character, check whether it is not a space.

Only non-space characters can belong to a segment. 4. If the current character is not a space, determine whether it starts a new segment.

A character starts a new segment if:

  • it is at index 0, meaning the string starts with a segment, or
  • the previous character is a space
  1. If either condition is true, increment count.

This guarantees that each segment is counted exactly once, at its first character. 6. Continue until the entire string has been processed. 7. Return count.

Why it works

The algorithm relies on the invariant that every segment has exactly one starting character. A segment starts when a non-space character either appears at the beginning of the string or immediately follows a space. By counting only these starting positions, the algorithm counts every segment exactly once and never overcounts consecutive characters within the same segment.

Python Solution

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

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

        return count

The implementation begins by initializing count to zero. This variable tracks how many segment starts have been found.

The loop iterates through every index in the string. For each character, the code first checks whether the character is a non-space character. If it is a space, it cannot begin a segment, so the iteration continues.

When a non-space character is found, the code checks whether it is the beginning of a new segment. This occurs when the character is at index 0 or when the previous character is a space. If either condition is true, the counter is incremented.

After the loop finishes, the function returns the total number of detected segment starts, which equals the number of segments.

Go Solution

func countSegments(s string) int {
    count := 0

    for i := 0; i < len(s); i++ {
        if s[i] != ' ' {
            if i == 0 || s[i-1] == ' ' {
                count++
            }
        }
    }

    return count
}

The Go implementation follows the exact same logic as the Python version. Since strings in Go are indexable by byte, iterating through the string using indices works correctly here because the problem guarantees only standard ASCII characters and spaces.

There are no special concerns about integer overflow because the maximum string length is only 300. Empty strings are naturally handled because the loop simply executes zero times.

Worked Examples

Example 1

Input:

s = "Hello, my name is John"

We scan the string character by character.

Index Character Previous Character New Segment? Count
0 H None Yes 1
1 e H No 1
2 l e No 1
3 l l No 1
4 o l No 1
5 , o No 1
6 space , No 1
7 m space Yes 2
8 y m No 2
9 space y No 2
10 n space Yes 3
11 a n No 3
12 m a No 3
13 e m No 3
14 space e No 3
15 i space Yes 4
16 s i No 4
17 space s No 4
18 J space Yes 5
19 o J No 5
20 h o No 5
21 n h No 5

Final answer:

5

Example 2

Input:

s = "Hello"
Index Character Previous Character New Segment? Count
0 H None Yes 1
1 e H No 1
2 l e No 1
3 l l No 1
4 o l No 1

Final answer:

1

Complexity Analysis

Measure Complexity Explanation
Time O(n) The string is traversed exactly once
Space O(1) Only a few variables are used

The algorithm performs a single linear scan through the string, making the time complexity proportional to the length of the input. No additional data structures are allocated, so the extra memory usage remains constant regardless of input size.

Test Cases

solution = Solution()

assert solution.countSegments("Hello, my name is John") == 5  # standard example
assert solution.countSegments("Hello") == 1  # single word
assert solution.countSegments("") == 0  # empty string
assert solution.countSegments("    ") == 0  # only spaces
assert solution.countSegments("a") == 1  # single character segment
assert solution.countSegments(" a") == 1  # leading space
assert solution.countSegments("a ") == 1  # trailing space
assert solution.countSegments(" a ") == 1  # leading and trailing spaces
assert solution.countSegments("hello   world") == 2  # multiple spaces between words
assert solution.countSegments("one two  three   four") == 4  # irregular spacing
assert solution.countSegments("!@# $%^") == 2  # punctuation characters
assert solution.countSegments("abc123 def456") == 2  # alphanumeric segments
assert solution.countSegments("   multiple   spaces   everywhere   ") == 3  # many extra spaces
Test Why
"Hello, my name is John" Validates normal multi-word input
"Hello" Validates single segment case
"" Validates empty input
" " Validates all-space input
"a" Validates minimal non-empty input
" a" Validates leading spaces
"a " Validates trailing spaces
" a " Validates leading and trailing spaces together
"hello world" Validates multiple consecutive spaces
"one two three four" Validates irregular spacing
"!@# $%^" Validates punctuation handling
"abc123 def456" Validates alphanumeric content
" multiple spaces everywhere " Validates complex spacing patterns

Edge Cases

Empty String

An empty string contains no characters, so it cannot contain any segments. A buggy implementation might accidentally assume at least one segment exists. In this solution, the loop never executes when the string is empty, so the counter correctly remains 0.

Multiple Consecutive Spaces

Strings may contain several spaces in a row, such as "hello world". A naive implementation that counts spaces and adds one could incorrectly overcount segments. This solution avoids that issue by counting only transitions from a space to a non-space character.

Leading and Trailing Spaces

Inputs like " hello world " can cause bugs if the implementation assumes the first or last characters are always part of a segment. The algorithm handles this correctly because it only increments the count when it encounters a non-space character that begins a segment. Extra spaces at either end are ignored naturally.

String Containing Only Spaces

An input such as " " has no valid segments even though the string is non-empty. Some implementations mistakenly count empty substrings as words. Since this solution only counts non-space characters that begin segments, the result correctly remains 0.