algoadvance

Leetcode 434. Number of Segments in a String

Problem Statement

You are 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.

For example:

Input: "Hello, my name is John"
Output: 5

Clarifying Questions

To ensure we understand the requirements correctly, we might ask:

  1. Can the input string have leading or trailing spaces?
  2. Can there be multiple spaces between segments?
  3. Are there any constraints on the length of the input string?
  4. What should be returned if the string is empty or contains only spaces?

Answering these questions based on common scenarios:

  1. Yes, the input string can have leading or trailing spaces.
  2. Yes, there can be multiple spaces between segments.
  3. Constraints are typical, up to (10^5) characters.
  4. If the string is empty or contains only spaces, the output should be 0.

Strategy

To solve this problem, the strategy generally involves:

  1. Traverse through the string while looking for the start and end of segments.
  2. Use a simple loop to iterate through the characters of the string.
  3. Count transitions from a space character to a non-space character as the start of a new segment.
  4. Handle edge cases like empty strings or strings with only spaces.

Code

Here is the C++ code to solve the problem:

#include <iostream>
#include <string>

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

// Example Usage
int main() {
    Solution solution;
    std::string testString = "Hello, my name is John";
    std::cout << "Number of Segments: " << solution.countSegments(testString) << std::endl;
    return 0;
}

Time Complexity

The time complexity of this solution is (O(n)), where (n) is the length of the string. This is because we perform a single pass over the string to count the segments.

Summary

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