1816. Truncate Sentence
Model: qwen2.5-coder:14b
Topics: String
FAANG asked: 0
Acceptance rate: 78.9%
Problem Breakdown
The problem requires truncating a given sentence s such that it contains only the first k words. The input consists of a string s representing the sentence and an integer k indicating how many words to keep. The output should be the truncated sentence as a string.
Inputs:
- A string
s: A sentence with words separated by single spaces. - An integer
k: The number of words to retain in the sentence.
Outputs:
- A string: The truncated sentence containing only the first
kwords.
Implicit Constraints or Edge Cases:
- If
kis 1, return only the first word. - If
kequals the total number of words ins, return the entire sentence. - The sentence will not have leading or trailing spaces, and words are separated by exactly one space.
Intuition
A brute-force approach would involve splitting the string into a list of words, taking the first k words, and then joining them back into a string. This approach is straightforward but has a time complexity of O(n) due to the split and join operations, where n is the length of the string.
The key insight is that we can avoid creating an intermediate list by iterating through the string character by character and counting spaces until we reach the k-th space. At this point, we can return the substring from the start up to (but not including) the current position. This approach reduces the space complexity to O(1) since we are not using any additional data structures.
Approach
- Initialize a counter
word_countto 0 and a variableend_indexto -1. - Iterate through each character in the string
s. - If a space is encountered, increment
word_count. - If
word_countequalsk, setend_indexto the current index and break out of the loop. - After the loop, if
end_indexis still -1, it means we need the entire string (i.e.,kis equal to the number of words ins). - Return the substring from the start of
sup toend_index.
Complexity Analysis
- Time Complexity: O(n), where n is the length of the string
s. We iterate through the string once. - Space Complexity: O(1). We use a constant amount of extra space.
Solution
def truncateSentence(s: str, k: int) -> str:
word_count = 0
end_index = -1
for i in range(len(s)):
if s[i] == ' ':
word_count += 1
if word_count == k:
end_index = i
break
# If end_index is still -1, it means we need the entire string
return s[:end_index] if end_index != -1 else s
Edge Cases Handled
- Single Word (
k=1): The loop will find the first space and setend_indexto 0, returning only the first word. - All Words (
kequals number of words ins): The loop completes without settingend_index, so the entire string is returned. - No Spaces (Single Word Sentence): The loop doesn’t execute, and the entire string is returned.