Leetcode 1816. Truncate Sentence Solution

Problem Explanation

Given a sentence s and an integer k, the task is to truncate the sentence such that it contains only the first k words, and return that truncated sentence.

A sentence is a list of words separated by a single space with no leading or trailing spaces. Each word consists of uppercase and lowercase English letters only (no punctuation).

Example

Consider the example with s = "Hello how are you Contestant" and k = 4.

The words in the sentence are ["Hello", "how" "are", "you", "Contestant"]. The first 4 words are ["Hello", "how", "are", "you"]. So the output should be "Hello how are you".

Approach

One simple approach to solve this problem is by iterating through the sentence character by character and counting the spaces. Once we encounter k - 1 spaces, we truncate the sentence and return the substring.

Example Walkthrough

Let's use the previous example with s = "Hello how are you Contestant" and k = 4.

  1. Iterate through the sentence, keeping a counter for spaces.
  2. At each character, check if the character is a space.
  3. When we encounter the k - 1 = 3'rd space, we truncate the sentence (i.e., create a substring from the beginning until this space, excluding the space).
  4. Return the truncated sentence.

After iterating through the characters, we find the 3rd space at position 15 ("Hello how are| you Contestant"). So the truncated sentence is s.substr(0, 15) which is "Hello how are you".

Solution

C++

1class Solution {
2public:
3    string truncateSentence(string s, int k) {
4        for (int i = 0; i < s.length(); ++i) {
5            if (s[i] == ' ' && --k == 0) {
6                return s.substr(0, i); // Truncate the sentence when k spaces are encountered
7            }
8        }
9        return s;
10    }
11};

Python

1class Solution:
2    def truncateSentence(self, s: str, k: int) -> str:
3        for i in range(len(s)):
4            if s[i] == ' ':
5                k -= 1
6            if k == 0:
7                return s[:i] # Truncate the sentence when k spaces are encountered
8        return s

Java

1class Solution {
2    public String truncateSentence(String s, int k) {
3        for (int i = 0; i < s.length(); ++i) {
4            if (s.charAt(i) == ' ' && --k == 0) {
5                return s.substring(0, i); // Truncate the sentence when k spaces are encountered
6            }
7        }
8        return s;
9    }
10}

JavaScript

1class Solution {
2    truncateSentence(s, k) {
3        for (let i = 0; i < s.length; ++i) {
4            if (s[i] === ' ' && --k === 0) {
5                return s.substring(0, i); // Truncate the sentence when k spaces are encountered
6            }
7        }
8        return s;
9    }
10}

C#

1public class Solution {
2    public string TruncateSentence(string s, int k) {
3        for (int i = 0; i < s.Length; ++i) {
4            if (s[i] == ' ' && --k == 0) {
5                return s.Substring(0, i); // Truncate the sentence when k spaces are encountered
6            }
7        }
8        return s;
9    }
10}

Complexity Analysis

The solution has a time complexity of O(n), where n is the length of the sentence, since we iterate through the sentence character by character. The space complexity is also O(n) due to the output truncated sentence. If we are allowed to modify the input sentence in place, the space complexity can be reduced to O(1).