Want Help Cracking FAANG?

(Then click this)

 ×
Back to Question Bank

1816. Truncate Sentence - Leetcode Solution

Code Implementation

class Solution:
    def truncateSentence(self, s: str, k: int) -> str:
        return ' '.join(s.split()[:k])
      
class Solution {
public:
    string truncateSentence(string s, int k) {
        int count = 0;
        string result;
        for (char c : s) {
            if (c == ' ') {
                count++;
                if (count == k) break;
            }
            result += c;
        }
        return result;
    }
};
      
class Solution {
    public String truncateSentence(String s, int k) {
        String[] words = s.split(" ");
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < k; i++) {
            if (i > 0) sb.append(" ");
            sb.append(words[i]);
        }
        return sb.toString();
    }
}
      
var truncateSentence = function(s, k) {
    return s.split(" ").slice(0, k).join(" ");
};

Problem Description

You are given a string s representing a sentence, and an integer k. Your task is to return a truncated version of the sentence that contains only the first k words. Words in the sentence are separated by single spaces, and there are no leading or trailing spaces. The output should be a string with exactly the first k words from s, separated by single spaces, and nothing more.

Thought Process

At first, it might seem like we need to manually parse the string and count words, but most programming languages provide built-in string manipulation functions that make this task easier. The main challenge is to extract exactly the first k words efficiently and assemble them back into a valid sentence. We want to avoid unnecessary complexity and make use of language features to keep our solution clean and concise.

Solution Approach

The solution can be broken down into simple, logical steps:
  • Step 1: Split the input string s into a list (or array) of words using the space character as the separator. This gives us an ordered collection of all words in the sentence.
  • Step 2: Select only the first k words from this list. This can be done by slicing or iterating up to k.
  • Step 3: Join the selected words back into a single string, with spaces in between, to form the truncated sentence.

This approach leverages the fact that splitting and joining strings are very efficient and readable operations in most languages. There is no need to manually count spaces or characters unless you want to avoid using built-in functions, but for clarity and speed, built-ins are preferred here.

Example Walkthrough

Let's walk through an example:

  • Input: s = "Hello how are you Contestant", k = 4
  • Step 1: Split s into words: ["Hello", "how", "are", "you", "Contestant"]
  • Step 2: Take the first 4 words: ["Hello", "how", "are", "you"]
  • Step 3: Join them with spaces: "Hello how are you"
  • Output: "Hello how are you"

The process is straightforward and works for any valid input as described by the problem.

Time and Space Complexity

  • Brute-force Approach: If you were to manually iterate through the string, counting spaces and collecting characters until k words have been found, the time complexity would still be O(n), where n is the length of the string. Space complexity would also be O(n) for storing the result.
  • Optimized Approach (using split/join): Splitting the string and joining the words both take O(n) time and space, since every character is processed once. Thus, time complexity is O(n) and space complexity is O(n).

In both approaches, the bottleneck is processing the entire input string at least once, so O(n) is optimal.

Summary

The problem asks us to extract the first k words from a sentence. By leveraging built-in string manipulation functions like split and join, we can solve the problem in a clean, readable, and efficient way. The solution is optimal in both time and space, and demonstrates the power of using standard library features for simple text processing tasks.