Truncate Sentence - Video Solutions

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.