algoadvance

Leetcode 1816. Truncate Sentence

Problem Statement

You are given a sentence s and an integer k. You need to return a string containing the first k words from the given sentence.

Example

Constraints

Clarifying Questions

  1. What separators are used in the sentences?
    The sentence uses spaces to separate words.

  2. Can the input string be empty or contain any special characters?
    No, the input string will not be empty and will only contain words with English letters separated by spaces.

  3. Is leading or trailing whitespace a concern to handle?
    No, the problem guarantees that the input sentence does not have leading or trailing whitespace.

Strategy

  1. Split the Sentence: Use the split(" ") method to break the sentence into an array of words.
  2. Select the First k Words: Use array slicing or a similar method to take the first k elements from the array.
  3. Join the Words: Use String.join(" ", parts) to join the selected first k words back into a single string.

Time Complexity

  1. Splitting the Sentence: The split operation is O(n), where n is the length of the sentence string.
  2. Slicing the Array: This operation is O(k).
  3. Joining the Words: This operation is O(k).

Overall, the time complexity is O(n + k).

Code

Here is the Java code implementing the above logic:

public class TruncateSentence {
    public String truncateSentence(String s, int k) {
        // Split the sentence into an array of words
        String[] words = s.split(" ");
        
        // Use StringBuilder to efficiently build the output string
        StringBuilder truncated = new StringBuilder();
        
        // Append the first k words to the string builder
        for (int i = 0; i < k; i++) {
            truncated.append(words[i]);
            // Add a space after each word except the last word
            if (i < k - 1) {
                truncated.append(" ");
            }
        }
        
        // Convert StringBuilder to String and return
        return truncated.toString();
    }

    public static void main(String[] args) {
        TruncateSentence ts = new TruncateSentence();
        System.out.println(ts.truncateSentence("Hello how are you Contestant", 4)); // "Hello how are you"
    }
}

This solution efficiently handles the truncation of the sentence and ensures that the first k words are returned as expected.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI