Number of Segments in a String

Difficulty: Easy | Acceptance: 37.30% | Paid: No Topics: String

Given a string s, return the number of segments in the string.

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

• Examples
• Constraints
• Built-in Split
• Linear Scan (State Machine)
• Two Pointers

Examples

Example 1

Input:

s = "Hello, my name is John"

Output:

5

Explanation: The five segments are [“Hello,”, “my”, “name”, “is”, “John”]

Example 2

Input:

s = "Hello"

Output:

1

Constraints

0 <= s.length <= 300
s consists of English letters, digits, symbols, and spaces.

Built-in Split

Intuition Most programming languages provide a built-in method to split strings by a delimiter (whitespace in this case). We can split the string and count the resulting non-empty tokens.

Steps

• Trim leading and trailing whitespace from the string.
• If the string is empty after trimming, return 0.
• Split the string by one or more whitespace characters.
• Return the length of the resulting array.

class Solution:
    def countSegments(self, s: str) -> int:
        # split() without arguments splits by any whitespace and ignores empty strings
        return len(s.split())

Complexity

• Time: O(n) - Splitting the string requires iterating through all characters.
• Space: O(n) - In the worst case, we store the entire string in an array of segments.
• Notes: This approach is concise and readable but uses extra space proportional to the input size.

Linear Scan (State Machine)

Intuition We can iterate through the string character by character. We maintain a state indicating whether we are currently inside a segment. We increment the counter only when we transition from a space to a non-space character.

Steps

• Initialize segmentCount to 0 and inSegment to false.
• Iterate through each character in the string.
• If the current character is not a space:
  • If we are not currently inSegment, increment segmentCount and set inSegment to true.
• If the current character is a space:
  • Set inSegment to false.
• Return segmentCount.

class Solution:
    def countSegments(self, s: str) -> int:
        count = 0
        in_segment = False
        
        for char in s:
            if char != ' ':
                if not in_segment:
                    count += 1
                    in_segment = True
            else:
                in_segment = False
                
        return count

Complexity

• Time: O(n) - We traverse the string exactly once.
• Space: O(1) - We only use a few variables for state and counting.
• Notes: This is the most space-efficient approach as it avoids creating an auxiliary array.

Two Pointers

Intuition We can use a pointer to traverse the string. We skip any leading spaces. When we find a non-space character, we have found a new segment. We then skip all subsequent non-space characters to find the end of the current segment, and repeat the process.

Steps

• Initialize i to 0 and count to 0.
• While i is less than the string length:
  • Skip all space characters by incrementing i.
  • If i is still within bounds (meaning we found a non-space char), increment count.
  • While i is within bounds and the character at i is not a space, increment i (move to the end of the segment).
• Return count.

class Solution:
    def countSegments(self, s: str) -> int:
        n = len(s)
        i = 0
        count = 0
        
        while i < n:
            # Skip spaces
            while i < n and s[i] == ' ':
                i += 1
            
            # If we found a non-space character, it's a new segment
            if i < n:
                count += 1
                
            # Skip the non-space characters of the current segment
            while i < n and s[i] != ' ':
                i += 1
                
        return count

Complexity

• Time: O(n) - Each character is visited at most twice (once by the outer loop logic, once by the inner skip logic).
• Space: O(1) - No extra space is used apart from pointers and counters.
• Notes: This approach effectively mimics how a parser might tokenize the input string.