Leet Code — 1816. Truncate Sentence

It’s an easy problem on leet code, description being:

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.

Constraints:

1 <= s.length <= 500
k is in the range [1, the number of words in s].
s consist of only lowercase and uppercase English letters and spaces.
The words in s are separated by a single space.
There are no leading or trailing spaces.

There is many different was of getting this done. You can split the String and concatenate what’s needed through a builder or using collector.

If you don’t want to split it, there is no much memory and want to be more fast forward, you can just iterate the string and add on a string builder, add a counter and leave when is done. Let’s try the first example, then compare with the second one:

class Solution {
    public String truncateSentence(String s, int k) {

        final String[] splittedS = s.split(" ");
        final StringBuilder response = new StringBuilder();

        response.append(splittedS[0]);

        for(int i=1;i<k;i++){
            response.append(" " + splittedS[i]);
        }

        return response.toString();
    }
}

Runtime: 2 ms, faster than 50.49% of Java online submissions for Truncate Sentence.

Memory Usage: 41.2 MB, less than 41.55% of Java online submissions for Truncate Sentence.

In the first example I did split the string, created a string builder which is faster than just concatenating multiple strings (due to string instance creation every concatenation), added the first one, then iterated the split and appended space.

On the second example I did the same but instead of using a default for, I’ve changed to stream, which can reduce boilerplate.

class Solution {
    public String truncateSentence(String s, int k) {


        // splitting the string
        final String[] splittedS = s.split(" ");

        // trimming the items that will not be used
        final String[] trimmedArray = Arrays.copyOfRange(splittedS, 0, k);

        // adding as stream and joining using space
        return Stream.of(trimmedArray).collect(Collectors.joining(" "));

        /* 
            one liner would be: 
            return Stream.of(Arrays.copyOfRange(s.split(" "), 0, k)).collect(Collectors.joining(" "));
        */        
    }
}

Runtime: 3 ms, faster than 35.12% of Java online submissions for Truncate Sentence.

Memory Usage: 40.9 MB, less than 71.04% of Java online submissions for Truncate Sentence.

As you can see, looks more simple, can be done in one line, but the performance is different.

The last example that I will show is basically no split and with the string builder, I believe is the fastest because there is no memory excess, but the idea is the same.

class Solution {
    public String truncateSentence(String s, int k) {

        final StringBuilder response = new StringBuilder();
        int count = 0;

        for(int i=0;i<s.length();i++){
            final char c = s.charAt(i);
            if(' ' == c) {
                count++;
                if(count==k) break;
            }
            response.append(c);
        }
        return response.toString();
    }
}

Runtime: 1 ms, faster than 84.40% of Java online submissions for Truncate Sentence.

Memory Usage: 40.6 MB, less than 91.06% of Java online submissions for Truncate Sentence.

All of the examples are O(n), due one iteration of a list and as the result showed the last one is faster and use less memory so would be the recommended one.

---

That’s it! If there is anything thing else to discuss feel free to drop a comment, until next post! :)