Number of Segments in a String - Solution & Explanation
Problem Statement
Given a string s, return the number of segments in the string.
A segment is defined to be a contiguous sequence of non-space characters.
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 <= 300sconsists of lowercase and uppercase English letters, digits, or one of the following characters"!@#$%^&*()_+-=',.:".- The only space character in
sis' '.
Approach Overview
Problem Overview: You receive a string that may contain words separated by one or more spaces. A segment is defined as a contiguous sequence of non-space characters. The task is to count how many such segments exist in the string.
Approach 1: Splitting Based on Spaces (O(n) time, O(n) space)
This approach uses the built-in split() function available in most languages. Splitting the string on spaces produces an array of tokens, where each token represents a potential word. Because multiple spaces can appear between words, you must filter out empty strings before counting. Internally, the runtime scans the entire string once to create substrings, which makes the time complexity O(n). The additional array of tokens requires O(n) auxiliary space.
This method is concise and readable. It works well in scripting or production environments where clarity matters more than micro-optimizations. Since the problem revolves around parsing a string, built-in splitting utilities are often the fastest way to express the solution.
Approach 2: Manual Counting with Iteration (O(n) time, O(1) space)
A more interview-focused approach scans the string character by character and counts the start of each segment. A new segment begins when the current character is not a space and either it is the first character in the string or the previous character is a space. Every time this condition appears, increment the counter. This detects transitions from space to non-space characters.
The algorithm performs a single linear pass over the string using a simple loop, giving O(n) time complexity. It only stores a counter and a few temporary variables, so the extra space is O(1). This technique is a classic pattern in string traversal problems where you detect boundaries between tokens without allocating additional data structures.
Recommended for interviews: Manual counting with iteration is typically what interviewers expect. It shows that you understand how segments are formed and can detect word boundaries during a single scan. The split-based solution demonstrates familiarity with language utilities, but the iterative approach proves stronger algorithmic reasoning and better space efficiency.
Approach 1: Splitting Based on Spaces
One efficient way to determine the number of segments in a string is to utilize its built-in split method, which divides the string into parts based on spaces. The segments will represent contiguous sequences of non-space characters. This approach handles all continuous whitespaces correctly by filtering out empty strings in the resulting list or array.
This C code utilizes the strtok function to tokenize the string s based on spaces. For each token found, the count is incremented. This correctly identifies contiguous groups of non-space characters.
Complexity
Time Complexity: O(n), where n is the length of the string. Space Complexity: O(1), using in-place manipulation.
Approach 2: Manual Counting with Iteration
This approach iteratively examines the characters of the string to manually count segments. We increment the segment count every time we encounter the start of a segment: a non-space character that was preceded by a space or the start of the string.
This code manually iterates over each character of the string. The boolean flag inSegment helps track when we are entering a new segment, ensuring we correctly count the number of contiguous non-space character groups.
Complexity
Time Complexity: O(n), iterating over the string once. Space Complexity: O(1), as no additional storage beyond a few variables is needed.
Approach 3: String Splitting
We split the string s by spaces and then count the number of non-empty words.
The time complexity is O(n), and the space complexity is O(n), where n is the length of the string s.
Approach 4: Simulation
We can also directly traverse each character s[i] in the string. If s[i] is not a space and s[i-1] is a space or i = 0, then s[i] marks the beginning of a new word, and we increment the answer by one.
After the traversal, we return the answer.
The time complexity is O(n), where n is the length of the string s. The space complexity is O(1).
Complexity Comparison
| Approach | Complexity |
|---|---|
| Splitting Based on Spaces | Time Complexity: O(n), where n is the length of the string. Space Complexity: O(1), using in-place manipulation. |
| Manual Counting with Iteration | Time Complexity: O(n), iterating over the string once. Space Complexity: O(1), as no additional storage beyond a few variables is needed. |
| String Splitting | — |
| Simulation | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Splitting Based on Spaces | O(n) | O(n) | Quick implementation using built-in string split utilities |
| Manual Counting with Iteration | O(n) | O(1) | Preferred in interviews or memory-constrained scenarios |
Video Solution
LeetCode 434. Number of Segments in a String Solution Explained - Java • Nick White • 5,572 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Number of Segments in a String easy or hard?
Number of Segments in a String Python/Java solution
How to solve Number of Segments in a String in O(n)?
What is the best approach for Number of Segments in a String?
Is Number of Segments in a String asked at Google/Amazon/Meta?
What data structure is used in Number of Segments in a String?
What is the time complexity of Number of Segments in a String?
Ready to solve this problem?
Practice Number of Segments in a String with our built-in code editor and test cases.
Practice on FleetCodeTable of Contents
Practice this problem
Open in Editor