Problem. A sentence is a list of words separated by single spaces, with no leading or trailing spaces. Given a sentence s and an integer k, return the sentence made of only its first k words.
Two clean approaches
The obvious approach splits the string into words and joins the first k:
def truncateSentence(s, k): return " ".join(s.split(" ")[:k])
That is O(n) time and O(n) extra space for the list of words. It is perfectly acceptable, but an interviewer may ask whether you can avoid building the list.
The second approach scans for spaces. The k-th space marks the end of the answer, so slice right before it. If there are fewer than k spaces, the whole sentence is the answer.
def truncateSentence(s, k): for i, ch in enumerate(s): if ch == " ": k -= 1 if k == 0: return s[:i] return s
This is still O(n) time, but it stops early and only allocates the result.
Things to mention out loud
- The constraints guarantee single spaces and no padding, which is what makes counting spaces safe. If the input could have repeated spaces, you would need to skip runs of spaces.
- Edge case:
kequals the number of words, so the loop ends without returning and you returnsunchanged.
I write these short walkthroughs while working on Linkjob AI, a tool that helps candidates during live interviews. (Disclosure: I'm part of the Linkjob AI team.)