Jobs

Interviews

Discussions

Number of Segments in a String

Easy

Asked by:

12 views

Topics:

Strings

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 <= 300
s consists of lowercase and uppercase English letters, digits, or one of the following characters "!@#$%^&*()_+-=',.:".
The only space character in s is ' '.

Try coding it in LeetCode

Number of Segments in a String

Easy

Asked by:

12 views

Topics:

Strings

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 <= 300
s consists of lowercase and uppercase English letters, digits, or one of the following characters "!@#$%^&*()_+-=',.:".
The only space character in s is ' '.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the input string `s` be null or empty?
Does leading or trailing whitespace in `s` count as a segment, or should I trim it?
Can there be multiple consecutive spaces between words? If so, how should I handle them?
Besides spaces, are there any other characters that could be considered delimiters between segments, or is it strictly spaces?
What should I return if the string contains only spaces?

Brute Force Solution

Approach

The goal is to count how many separate 'words' are in a sentence. The brute force way is to go through each part of the sentence and carefully decide if that part starts a new word.

Here's how the algorithm would work step-by-step:

Start at the very beginning of the sentence.
Look at each character one by one, moving from left to right.
If you find a space, that might mean a new word is starting soon.
The character AFTER the space is potentially the beginning of a new word; check if it is not a space itself.
Every time you find a character that's not a space, and it follows a space, count it as the start of a new word.
At the very end, the final count will be the number of segments.

Code Implementation

def count_segments_brute_force(input_string):
    segment_count = 0
    string_length = len(input_string)

    for index in range(string_length):
        # Check for non-space character
        if input_string[index] != ' ':

            # Check if it's the start of a new segment.
            if index == 0 or input_string[index - 1] == ' ':
                segment_count += 1

    return segment_count

Big(O) Analysis

Time Complexity

O(n) – The provided solution iterates through the string once, examining each character to determine if it marks the beginning of a new segment. This single pass through the input string, where each character is inspected once, is directly proportional to the length of the string. Thus, the time complexity is determined by 'n', the length of the input string, leading to a linear time complexity of O(n).

Space Complexity

O(1) – The provided solution iterates through the string and uses a counter to track the number of segments. It does not create any auxiliary data structures like arrays, lists, or hash maps. The space used is limited to a few integer variables (like the counter and potentially an index), which remains constant irrespective of the input string size, N. Therefore, the space complexity is O(1).

Optimal Solution

Approach

The problem asks us to count how many separated groups of characters (segments) are in a string, where segments are separated by spaces. The clever idea is to simply walk through the string and count the number of times a segment begins. A segment begins when a non-space character appears after a space, or at the very start of the string.

Here's how the algorithm would work step-by-step:

Look at each character in the string, one by one, going from left to right.
If you find a character that isn't a space, check if it's the first character in the string, or if the character right before it was a space.
If either of those things are true, then you've found the start of a new segment. Add one to your count.
Keep going until you've looked at every character in the string.
The final count is the number of segments in the string.

Code Implementation

def countSegments(input_string):
    segment_count = 0
    string_length = len(input_string)

    for i in range(string_length):
        # Check if current char is not space.
        if input_string[i] != ' ':

            # If it's the first char or preceded by space.
            if i == 0 or input_string[i - 1] == ' ':
                # Found a new segment.
                segment_count += 1

    return segment_count

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input string of length n exactly once, examining each character. For each character, it performs a constant amount of work: checking if it's a space and, if not, checking its preceding character. Therefore, the time complexity is directly proportional to the length of the string, resulting in O(n).

Space Complexity

O(1) – The algorithm iterates through the input string, but it does not create any auxiliary data structures like arrays, hash maps, or lists to store intermediate results. It only uses a counter variable to keep track of the number of segments. Therefore, the amount of extra memory used remains constant regardless of the input string's length N. The space complexity is O(1).

Edge Cases

Case	How to Handle
Empty string	Return 0 because there are no segments in an empty string.
String with only spaces	Return 0 because there are no non-space characters.
String starting with space(s)	Trim leading spaces or handle the first non-space character correctly in iteration.
String ending with space(s)	Trim trailing spaces or handle the last non-space character correctly in iteration.
String with multiple spaces between words	Count a new segment only after encountering a non-space character after a space.
String with one word and no spaces	Return 1 because there's one segment.
String with leading, trailing, and multiple internal spaces	Properly handle all space occurrences to count segments correctly.
Very long string to consider performance.	Iterative solutions should be efficient for long strings, avoid recursive solutions that cause stack overflow.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the input string `s` be null or empty?
Does leading or trailing whitespace in `s` count as a segment, or should I trim it?
Can there be multiple consecutive spaces between words? If so, how should I handle them?
Besides spaces, are there any other characters that could be considered delimiters between segments, or is it strictly spaces?
What should I return if the string contains only spaces?

Brute Force Solution

Approach

The goal is to count how many separate 'words' are in a sentence. The brute force way is to go through each part of the sentence and carefully decide if that part starts a new word.

Here's how the algorithm would work step-by-step:

Start at the very beginning of the sentence.
Look at each character one by one, moving from left to right.
If you find a space, that might mean a new word is starting soon.
The character AFTER the space is potentially the beginning of a new word; check if it is not a space itself.
Every time you find a character that's not a space, and it follows a space, count it as the start of a new word.
At the very end, the final count will be the number of segments.

Code Implementation

def count_segments_brute_force(input_string):
    segment_count = 0
    string_length = len(input_string)

    for index in range(string_length):
        # Check for non-space character
        if input_string[index] != ' ':

            # Check if it's the start of a new segment.
            if index == 0 or input_string[index - 1] == ' ':
                segment_count += 1

    return segment_count

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Look at each character in the string, one by one, going from left to right.
If you find a character that isn't a space, check if it's the first character in the string, or if the character right before it was a space.
If either of those things are true, then you've found the start of a new segment. Add one to your count.
Keep going until you've looked at every character in the string.
The final count is the number of segments in the string.

Code Implementation

def countSegments(input_string):
    segment_count = 0
    string_length = len(input_string)

    for i in range(string_length):
        # Check if current char is not space.
        if input_string[i] != ' ':

            # If it's the first char or preceded by space.
            if i == 0 or input_string[i - 1] == ' ':
                # Found a new segment.
                segment_count += 1

    return segment_count

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty string	Return 0 because there are no segments in an empty string.
String with only spaces	Return 0 because there are no non-space characters.
String starting with space(s)	Trim leading spaces or handle the first non-space character correctly in iteration.
String ending with space(s)	Trim trailing spaces or handle the last non-space character correctly in iteration.
String with multiple spaces between words	Count a new segment only after encountering a non-space character after a space.
String with one word and no spaces	Return 1 because there's one segment.
String with leading, trailing, and multiple internal spaces	Properly handle all space occurrences to count segments correctly.
Very long string to consider performance.	Iterative solutions should be efficient for long strings, avoid recursive solutions that cause stack overflow.