Code Implementation

class Solution:
    def countSegments(self, s: str) -> int:
        # Split the string by whitespace and filter out empty strings
        return len(s.split())
      

class Solution {
public:
    int countSegments(string s) {
        int count = 0;
        int n = s.size();
        for (int i = 0; i < n; ++i) {
            if (s[i] != ' ' && (i == 0 || s[i-1] == ' ')) {
                count++;
            }
        }
        return count;
    }
};
      

class Solution {
    public int countSegments(String s) {
        int count = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) != ' ' && (i == 0 || s.charAt(i-1) == ' ')) {
                count++;
            }
        }
        return count;
    }
}
      

/**
 * @param {string} s
 * @return {number}
 */
var countSegments = function(s) {
    // Split the string by whitespace and filter out empty strings
    return s.split(/\s+/).filter(Boolean).length;
};
      

Problem Description

Given a string s, count the number of segments in the string. A segment is defined as a contiguous sequence of non-space characters. Segments are separated by one or more spaces.

For example, in the string "Hello, my name is John", there are 5 segments: "Hello,", "my", "name", "is", and "John".

• Input: A string s (may contain leading, trailing, or multiple consecutive spaces)
• Output: An integer representing the number of segments in s
• Constraints:
  • Segments are separated by spaces
  • Empty strings or strings with only spaces have 0 segments

Thought Process

The key to solving this problem is recognizing that segments are simply groups of characters separated by spaces. The naive approach might be to split the string by spaces and count the resulting pieces, but we need to be careful about consecutive spaces, leading, or trailing spaces, which can create empty strings.

For instance, splitting " hello world " by spaces gives several empty strings. We need to count only the non-empty pieces. Alternatively, we could iterate through the string and count when a new segment starts, which happens when we see a non-space character that follows a space or is at the start of the string.

The optimized approach avoids creating extra strings and works by simply counting segment boundaries as we scan the string.

Solution Approach

• Step 1: Initialize a counter to zero. This will keep track of the number of segments found.
• Step 2: Iterate through each character in the string s.
• Step 3: For each character, check if it is not a space and either it is the first character in the string or the previous character is a space. This means a new segment is starting.
• Step 4: If the condition is met, increment the counter.
• Step 5: After the loop, return the counter as the answer.

This approach is efficient because:

• It only scans the string once (O(n) time).
• It does not require extra space for storing split segments (O(1) space).
• It handles edge cases like multiple spaces and empty strings naturally.

Example Walkthrough

Consider the input: s = " Hello world "

1. Start with count = 0.
2. Characters at index 0 and 1 are spaces, so do nothing.
3. At index 2, character is 'H', previous character is a space. This is the start of a segment. Increment count to 1.
4. Continue through 'e', 'l', 'l', 'o' (all are part of the current segment).
5. At index 8-10, characters are spaces, so do nothing.
6. At index 11, character is 'w', previous character is a space. This is a new segment. Increment count to 2.
7. Continue through 'o', 'r', 'l', 'd'.
8. Characters at the end are spaces, so do nothing.
9. Final result: count = 2.

Time and Space Complexity

• Brute-force (splitting and filtering):
  • Time: O(n) to split and filter the string.
  • Space: O(n) for storing the split segments.
• Optimized approach (single pass):
  • Time: O(n), where n is the length of the string, since we scan each character once.
  • Space: O(1), only a few variables are used regardless of string size.

The optimized approach is preferred for large inputs because it uses minimal additional memory and is straightforward to implement.

Summary

To count the number of segments in a string, we scan through the string and count every time we encounter the start of a new segment (a non-space character following a space or at the beginning). This approach is elegant, efficient, and robust against tricky cases like multiple spaces or empty strings. The solution demonstrates the importance of understanding string traversal and boundary detection for simple yet powerful string processing tasks.