algoadvance

Leetcode 434. Number of Segments in a String

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.

Clarifying Questions

1. What is the definition of a segment in this context?
   • A segment is a contiguous sequence of non-space characters.
2. Will the input string s contain only ASCII characters?
   • For the purpose of this problem, yes, we assume s contains only ASCII characters.
3. Can the input string be empty?
   • Yes, the input string can be empty.
4. Are there any constraints on the length of the string?
   • For typical LeetCode problems, we assume the length is within reasonable bounds (e.g., up to (10^5) characters).

Strategy

1. Trim the String: Remove extra spaces from the beginning and end of the string to simplify processing.
2. Split the String: Use the space character as the delimiter to split the string.
3. Filter Empty Segments: Due to potential multiple spaces between words, after splitting, some segments may be empty. Filter them out.
4. Count the Segments: The number of non-empty segments is the result.

Code

public class Solution {
    public int countSegments(String s) {
        // Trim the input string to remove leading and trailing spaces
        s = s.trim();
        
        // If the trimmed string is empty, return 0
        if (s.isEmpty()) {
            return 0;
        }
        
        // Split the string by spaces
        String[] segments = s.split("\\s+");
        
        // Return the number of non-empty segments
        return segments.length;
    }
}

Time Complexity

• Time Complexity: (O(n))
  • Trimming the string and splitting it by spaces both operate in linear time relative to the length of the string.
• Space Complexity: (O(n))
  • In the worst case, additional space proportional to the length of the string is used for storing the segments array.

This strategy ensures efficient computation and handles edge cases effectively (e.g., multiple spaces).

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?