algoadvance

Leetcode 1816. Truncate Sentence

Problem Statement

Given a sentence s and an integer k, you need to return the sentence formed by the first k words of s.

Example:

Clarifying Questions

  1. What constitutes a word?
    • A word is any sequence of non-space characters.
  2. What is the range of values for k and the length of s?
    • The number of words k is guaranteed to be a positive integer ≤ the number of words in s.
    • The length of s will be at most 1000 characters.
  3. Are there any constraints on characters in s?
    • The sentence s consists of only lowercase and uppercase English letters and spaces.

Strategy

To solve this, we need to split the sentence s into words and then reconstruct the sentence using the first k words. Here are the steps:

  1. Split the input string s into words. - This can be done via string manipulation techniques.
  2. Construct the resulting string from the first k words.
  3. Return the constructed string.

Code

Here’s the implementation in C++:

#include <iostream>
#include <sstream>
#include <vector>

std::string truncateSentence(const std::string& s, int k) {
    std::istringstream iss(s);
    std::string word;
    std::vector<std::string> words;

    while (iss >> word) {
        words.push_back(word);
    }

    std::string result;
    for (int i = 0; i < k; ++i) {
        if (i != 0) result += " ";
        result += words[i];
    }

    return result;
}

// Example usage:
int main() {
    std::cout << truncateSentence("Hello how are you Contestant", 4) << std::endl; // Output: "Hello how are you"
    std::cout << truncateSentence("What is the solution to this problem", 4) << std::endl; // Output: "What is the solution to"
    std::cout << truncateSentence("chopper is not a tanuki", 5) << std::endl; // Output: "chopper is not a tanuki"
    return 0;
}

Time Complexity

The time complexity of this approach is O(n), where n is the length of the string s. This is because we are reading through the string once to split it into words and then another pass to construct the output string from the first k words. In the worst case, each character of the string s is visited twice.

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