Truncate Sentence solution and explanation
9 more videos on this problem
1816. Truncate Sentence | Leetcode Weekly Contest 236Ayushi Rawat · 3:19 · 1K views
Leetcode | 1816. Truncate Sentence | Easy | Java SolutionDeveloper Docs · 6:45 · 1K views
LeetCode 1816 : Truncate Sentence | Solution in C++Amit Manjarly · 5:57 · 516 views
1816. Truncate Sentence (Leetcode Easy)Programming Live with Larry · 2:41 · 445 views
LeetCode 1816 : Truncate Sentence | Solution in JAVAAmit Manjarly · 5:44 · 395 views
1816. Truncate Sentence with Python | Leetcode With Python #leetcode #youtube #pythontutorialArsalan Ahmed · 4:34 · 296 views
leetcode - 1816 Truncate Sentence with ExplanationlitCode · 11:53 · 229 views
1816. Truncate Sentence | Easy Level Question of leetcode Truncate Sentence 1816 | Solution in py3EduEverybody · 3:18 · 130 views
1816. Leetcode Truncate Sentence - EasySmile And Code · 8:51 · 110 views
Crack LeetCode 1816: Truncate Sentence in Minutes! [Easy Explanation]CodingForBeginners · 4:07 · 102 views
The problem
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 <= 500kis in the range[1, the number of words in s].sconsist of only lowercase and uppercase English letters and spaces.- The words in
sare separated by a single space. - There are no leading or trailing spaces.
Approach overview
Problem Overview: You receive a sentence s containing words separated by single spaces and an integer k. The task is to return a new string that contains only the first k words from the sentence. Words must remain in the original order and be separated by a single space.
Approach 1: Split and Join Method (O(n) time, O(n) space)
The straightforward solution uses built-in string utilities. Split the sentence into an array of words using the space delimiter. After that, take the first k elements and join them back into a string using spaces. The key operation is split(), which converts the sentence into a list of tokens. Then a slice or subarray operation selects the first k words before combining them with join(). Time complexity is O(n) because the entire string must be scanned during the split operation. Space complexity is also O(n) since the array of words is stored in memory. This approach is clean, readable, and typically the fastest to implement in interviews or production code when memory constraints are not strict. It relies heavily on standard string manipulation functions available in most languages.
Approach 2: In-place Scan / Character Iteration (O(n) time, O(1) extra space)
A more memory-efficient method scans the sentence character by character and counts spaces. Each space indicates the end of a word. Once you encounter the k-th word boundary, return the substring from index 0 up to that position. This avoids building an intermediate array of words. The algorithm simply iterates through the characters, increments a counter when encountering a space, and stops once k words have been processed. Time complexity remains O(n) because the string may need to be scanned entirely in the worst case. Space complexity is O(1) since only a few counters and indices are used. This approach demonstrates stronger control over memory and low-level operations on string data while avoiding unnecessary allocations. The iteration pattern is similar to linear traversal problems over arrays.
Recommended for interviews: Both approaches run in linear time, which is optimal because every character may need to be inspected. The split-and-join method is usually the quickest to implement and easiest to read, making it perfectly acceptable in most interviews. The in-place scanning approach shows deeper understanding of string traversal and space optimization, which can impress interviewers when they ask for improvements after the initial solution.
Approach 1: Split and Join Method
This approach involves splitting the sentence into words using the space as a delimiter and then joining the first k words back into a sentence.
def truncate_sentence(s, k):
return ' '.join(s.split()[:k])
s = "Hello how are you Contestant"
k = 4
print(truncate_sentence(s, k))public class TruncateSentence {
public static String truncateSentence(String s, int k) {
String[] words = s.split(" ");
StringBuilder result = new StringBuilder();
for (int i = 0; i < k; i++) {
if (i != 0) result.append(" ");
result.append(words[i]);
}
return result.toString();
}
public static void main(String[] args) {
String s = "Hello how are you Contestant";
int k = 4;
System.out.println(truncateSentence(s, k));
}
}#include <iostream>
#include <sstream>
using namespace std;
string truncateSentence(string s, int k) {
istringstream iss(s);
string word, result;
while (k-- && iss >> word) {
if (!result.empty()) result += " ";
result += word;
}
return result;
}
int main() {
string s = "Hello how are you Contestant";
int k = 4;
cout << truncateSentence(s, k) << endl;
return 0;
}function truncateSentence(s, k) {
return s.split(' ').slice(0, k).join(' ');
}
const s = "Hello how are you Contestant";
const k = 4;
console.log(truncateSentence(s, k));#include <stdio.h>
#include <string.h>
char* truncateSentence(char* s, int k) {
int wordCount = 0;
char* endPtr = s;
while (*endPtr) {
if (*endPtr == ' ') {
wordCount++;
if (wordCount == k) {
*endPtr = '\0';
break;
}
}
endPtr++;
}
return s;
}
int main() {
char s[] = "Hello how are you Contestant";
int k = 4;
printf("%s\n", truncateSentence(s, k));
return 0;
}using System;
public class TruncateSentence {
public static string TruncateSentence(string s, int k) {
string[] words = s.Split(' ');
return string.Join(" ", words, 0, k);
}
public static void Main() {
string s = "Hello how are you Contestant";
int k = 4;
Console.WriteLine(TruncateSentence(s, k));
}
}The split() method divides the string into a list of words, and join() reconstructs a string with only the first k words. No additional spacing adjustments are necessary.
Time Complexity: O(n), Space Complexity: O(n)
Approach 2: In-place Modification
This method involves iterating over the characters of the string and directly modifying it to terminate at the end of the k-th word.
def truncate_sentence(s, k):
i = 0
for j, c in enumerate(s):
if c == ' ':
i += 1
if i == k:
return s[:j]
return s
s = "What is the solution to this problem"
k = 4
print(truncate_sentence(s, k))public class TruncateSentence {
public static String truncateSentence(String s, int k) {
int wordCount = 0, i = 0;
for (; i < s.length(); i++) {
if (s.charAt(i) == ' ') {
wordCount++;
if (wordCount == k) break;
}
}
return s.substring(0, i);
}
public static void main(String[] args) {
String s = "What is the solution to this problem";
int k = 4;
System.out.println(truncateSentence(s, k));
}
}#include <iostream>
using namespace std;
string truncateSentence(string s, int k) {
int count = 0, i = 0;
for (; i < s.length(); ++i) {
if (s[i] == ' ' && ++count == k) break;
}
return s.substr(0, i);
}
int main() {
string s = "What is the solution to this problem";
int k = 4;
cout << truncateSentence(s, k) << endl;
return 0;
}function truncateSentence(s, k) {
let count = 0, i;
for (i = 0; i < s.length; i++) {
if (s[i] === ' ') {
count++;
if (count === k) break;
}
}
return s.substring(0, i);
}
const s = "What is the solution to this problem";
const k = 4;
console.log(truncateSentence(s, k));#include <stdio.h>
#include <string.h>
char* truncateSentence(char* s, int k) {
int count = 0;
for (char* p = s; *p; ++p) {
if (*p == ' ') {
count++;
if (count == k) {
*p = '\0';
break;
}
}
}
return s;
}
int main() {
char s[] = "What is the solution to this problem";
int k = 4;
printf("%s\n", truncateSentence(s, k));
return 0;
}using System;
public class TruncateSentence {
public static string TruncateSentence(string s, int k) {
int spaceCount = 0;
for (int i = 0; i < s.Length; i++) {
if (s[i] == ' ') {
spaceCount++;
if (spaceCount == k) return s.Substring(0, i);
}
}
return s;
}
public static void Main() {
string s = "What is the solution to this problem";
int k = 4;
Console.WriteLine(TruncateSentence(s, k));
}
}In Python, we loop through characters and count spaces to determine where the string should be cut to form the truncated sentence.
Time Complexity: O(n), Space Complexity: O(1)
Approach 3: Simulation
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).
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;
}func truncateSentence(s string, k int) string {
for i, c := range s {
if c == ' ' {
k--
}
if k == 0 {
return s[:i]
}
}
return s
}Complexity comparison
| Approach | Complexity |
|---|---|
| Split and Join Method | Time Complexity: O(n), Space Complexity: O(n) |
| In-place Modification | Time Complexity: O(n), Space Complexity: O(1) |
| Simulation | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Split and Join Method | O(n) | O(n) | Best for readability and fast implementation using built-in string utilities |
| In-place Character Scan | O(n) | O(1) | Useful when minimizing memory allocations or demonstrating manual string traversal |
Frequently asked questions
Is Truncate Sentence easy or hard?
Truncate Sentence is classified as an Easy problem on LeetCode with a high acceptance rate above 80%. It primarily tests basic string manipulation, iteration, and understanding of word boundaries.
Truncate Sentence Python/Java solution
In Python, use s.split() to create a list of words and return ' '.join(words[:k]). In Java, use s.split(" ") and append the first k words with a StringBuilder or join them directly. Both implementations run in O(n) time.
How to solve Truncate Sentence in O(n)?
Iterate through the string and count spaces to detect word boundaries. Once the k-th word is reached, return the substring from index 0 to that position. This single-pass scan processes each character once, giving O(n) time complexity and O(1) extra space.
What is the best approach for Truncate Sentence?
The most practical approach is the split-and-join method. Split the sentence into words, take the first k elements, and join them back with spaces. It runs in O(n) time and O(n) space and is easy to implement in languages like Python, Java, and JavaScript.
Is Truncate Sentence asked at Google/Amazon/Meta?
Problems involving string parsing and word boundaries appear frequently in interviews at companies like Amazon, Google, and Meta. While this exact problem may appear less often, its pattern of scanning strings and handling delimiters is very common in coding interviews.
What data structure is used in Truncate Sentence?
The problem mainly relies on string processing. The split-based approach temporarily stores words in an array or list, while the in-place scanning approach works directly on the string without additional data structures.
What is the time complexity of Truncate Sentence?
The time complexity is O(n), where n is the length of the input string. Every character must be scanned at least once either during splitting or while iterating through the sentence to count spaces.