Skip to content

1816. Truncate Sentence

Description

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

  • For example, "Hello World", "HELLO", and "hello world hello world" are all sentences.

You are given a sentence s​​​​​​ and an integer k​​​​​​. You want to truncate s​​​​​​ such that it contains only the first k​​​​​​ words. Return s​​​​​​ after truncating it.

 

Example 1:

Input: s = "Hello how are you Contestant", k = 4
Output: "Hello how are you"
Explanation:
The words in s are ["Hello", "how", "are", "you", "Contestant"].
The first 4 words are ["Hello", "how", "are", "you"].
Hence, you should return "Hello how are you".

Example 2:

Input: s = "What is the solution to this problem", k = 4
Output: "What is the solution"
Explanation:
The words in s are ["What", "is" "the", "solution", "to", "this", "problem"].
The first 4 words are ["What", "is", "the", "solution"].
Hence, you should return "What is the solution".

Example 3:

Input: s = "chopper is not a tanuki", k = 5
Output: "chopper is not a tanuki"

 

Constraints:

  • 1 <= s.length <= 500
  • k is in the range [1, the number of words in s].
  • s consist of only lowercase and uppercase English letters and spaces.
  • The words in s are separated by a single space.
  • There are no leading or trailing spaces.

Solutions

Solution 1: String Split

Thinking

We must keep the first \(k\) words of a sentence. Splitting on spaces and joining them back is direct, at the cost of an intermediate word list.

The language's \(\textit{split}\) already tokenizes on whitespace; taking the first \(k\) tokens and joining with spaces matches the statement exactly.

Split the sentence by spaces, then join the first \(k\) words.

The time complexity is \(O(n)\), and the space complexity is \(O(n)\), where \(n\) is the length of \(s\).

1
2
3
class Solution:
    def truncateSentence(self, s: str, k: int) -> str:
        return ' '.join(s.split()[:k])

Solution 2: Simulation

Thinking

Solution 1 allocates an intermediate array. If we only need the cut position, scan left to right and decrement \(k\) on each space; when \(k\) hits \(0\) the current index is the space after the \(k\)-th word. If the scan ends with \(k>0\), the sentence has fewer than \(k\) words and we return it unchanged. Extra space drops to \(O(1)\).

We traverse the string \(s\) from the beginning. For the current character \(s[i]\), if it is a space, we decrement \(k\). When \(k\) becomes \(0\), it means that we have extracted \(k\) words, so we return the substring \(s[0..i)\).

After the traversal, we return \(s\).

The time complexity is \(O(n)\), where \(n\) is the length of the string \(s\). Ignoring the space complexity of the answer, the space complexity is \(O(1)\).

1
2
3
4
5
6
7
class Solution:
    def truncateSentence(self, s: str, k: int) -> str:
        for i, c in enumerate(s):
            k -= c == ' '
            if k == 0:
                return s[:i]
        return s

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

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
func truncateSentence(s string, k int) string {
    for i, c := range s {
        if c == ' ' {
            k--
        }
        if k == 0 {
            return s[:i]
        }
    }
    return s
}

1
2
3
4
5
6
7
8
function truncateSentence(s: string, k: number): string {
    for (let i = 0; i < s.length; ++i) {
        if (s[i] === ' ' && --k === 0) {
            return s.slice(0, i);
        }
    }
    return s;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
/**
 * @param {string} s
 * @param {number} k
 * @return {string}
 */
var truncateSentence = function (s, k) {
    for (let i = 0; i < s.length; ++i) {
        if (s[i] === ' ' && --k === 0) {
            return s.slice(0, i);
        }
    }
    return s;
};

Comments