# Truncate Sentence
**Difficulty:** EASY
[External](https://leetcode.com/problems/truncate-sentence)
Canonical: https://scaleengineer.com/dsa/problems/truncate-sentence
**Data structures:** Array, String
**Companies:** [Accenture](https://scaleengineer.com/companies/accenture)
---
## Problem
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._

**Example 1:**

**Input:** s = "Hello how are you Contestant", k = 4
**Output:** "Hello how are you"
**Explanation:**
The words in s are ["Hello", "how" "are", "you", "Contestant"].
The first 4 words are ["Hello", "how", "are", "you"].
Hence, you should return "Hello how are you".

**Example 2:**

**Input:** s = "What is the solution to this problem", k = 4
**Output:** "What is the solution"
**Explanation:**
The words in s are ["What", "is" "the", "solution", "to", "this", "problem"].
The first 4 words are ["What", "is", "the", "solution"].
Hence, you should return "What is the solution".

**Example 3:**

**Input:** s = "chopper is not a tanuki", k = 5
**Output:** "chopper is not a tanuki"

**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.

# Approaches
## Using String Split and Join
This approach utilizes built-in string manipulation functions to solve the problem. First, the sentence is split into an array of words based on the space delimiter. Then, a new sentence is constructed by taking only the first `k` words from this array and joining them back together with spaces.
**Time:** O(N), where N is the length of the input string `s`. The `split()` operation needs to scan the entire string, which takes O(N) time. Joining the first `k` words takes time proportional to the length of the resulting string, which is also bounded by O(N). · **Space:** O(N), where N is the length of the input string `s`. The `split()` method creates an array of words, and the total number of characters stored in this array is proportional to N. This is the dominant factor for auxiliary space.
**Pros:** The code is highly readable and straightforward, making it easy to understand and maintain.; It leverages standard library functions, which can reduce development time and potential bugs from manual implementation.
**Cons:** Inefficient in terms of memory usage because it creates an intermediate array to hold all the words of the original sentence.; Can be slower than a direct iteration approach due to the overhead of the `split` operation and creating a new array and a `StringBuilder`.
### Explanation
The core idea is to break down the problem into two main steps: splitting the sentence and then building the truncated version. Java's `String.split(" ")` method is perfect for the first step, as it returns an array of words. Once we have this array, we can easily access the first `k` words. We then use a `StringBuilder` for efficient string concatenation, iterating `k` times to append each of the first `k` words, followed by a space (except for the very last word). Finally, we convert the `StringBuilder` back to a string.

```java
class Solution {
    public String truncateSentence(String s, int k) {
        String[] words = s.split(" ");
        StringBuilder result = new StringBuilder();
        for (int i = 0; i < k; i++) {
            result.append(words[i]);
            if (i < k - 1) {
                result.append(" ");
            }
        }
        return result.toString();
    }
}
```
### Algorithm
1. Split the input string `s` into an array of strings `words` using the space character as the delimiter.
2. Create a `StringBuilder` to construct the result string.
3. Loop from `i = 0` to `k - 1`.
4. In each iteration, append the word `words[i]` to the `StringBuilder`.
5. If it's not the last word to be added (i.e., `i < k - 1`), append a space character.
6. After the loop, convert the `StringBuilder` to a string and return it.

## Single Pass Iteration
A more efficient approach is to perform a single pass over the input string. We can iterate through the string, keeping a count of the spaces we encounter. When the number of spaces equals `k`, we have found the point at which to truncate the string. This method avoids the overhead of creating an intermediate array of all the words.
**Time:** O(N), where N is the length of the input string `s`. In the worst-case scenario (when `k` is equal to the number of words in `s`), we have to traverse the entire string once. · **Space:** O(1) auxiliary space. We only use a few variables for the loop index and space counter, regardless of the input string's size. The space for the returned string is not considered auxiliary space.
**Pros:** Extremely space-efficient, using only O(1) auxiliary space.; Very time-efficient as it involves a single pass over the string and may terminate early if `k` is small.; Avoids the overhead of function calls like `split` and the creation of intermediate data structures.
**Cons:** The logic is slightly more complex to write manually compared to using high-level built-in functions.; Requires careful handling of indices and loop termination conditions to avoid off-by-one errors.
### Explanation
This approach optimizes for space by avoiding the creation of any significant intermediate data structures. We traverse the string from left to right. We only need one variable, `spaceCount`, to track how many words we have passed. Each time we see a space, we increment this counter. When `spaceCount` becomes equal to `k`, we know that the character right before this space was the end of the k-th word. We can then take the substring from the start of the string up to the index of this k-th space. If we iterate through the whole string and don't find `k` spaces, it means the total number of words is `k`, so the original string is the correct output.

```java
class Solution {
    public String truncateSentence(String s, int k) {
        int spaceCount = 0;
        for (int i = 0; i < s.length(); ++i) {
            if (s.charAt(i) == ' ') {
                spaceCount++;
                if (spaceCount == k) {
                    return s.substring(0, i);
                }
            }
        }
        // This case is reached if the number of words is k.
        return s;
    }
}
```
### Algorithm
1. Initialize a counter for spaces, `spaceCount`, to 0.
2. Iterate through the input string `s` character by character using an index `i`.
3. Inside the loop, check if the character `s.charAt(i)` is a space.
4. If it is a space, increment `spaceCount`.
5. After incrementing, check if `spaceCount` has reached `k`. If it has, it means we have found the end of the k-th word. The desired output is the substring from the beginning of the string up to the current index `i`. Return `s.substring(0, i)`.
6. If the loop completes without `spaceCount` reaching `k`, it means the sentence has exactly `k` words (as per the problem constraints). In this case, the entire original string `s` is the answer, so return `s`.

# Solutions
### Java

```java
class Solution {
public
  String truncateSentence(String s, int k) {
    for (int i = 0; i < s.length(); ++i) {
      if (s.charAt(i) == ' ' && (--k) == 0) {
        return s.substring(0, i);
      }
    }
    return s;
  }
}

```

### JavaScript

```javascript
/** * @param {string} s * @param {number} k * @return {string} */ var truncateSentence =
  function (s, k) {
    for (let i = 0; i < s.length; ++i) {
      if (s[i] === " " && --k === 0) {
        return s.slice(0, i);
      }
    }
    return s;
  };

```

### CPP

```cpp
class Solution {
public:
  string truncateSentence(string s, int k) {
    for (int i = 0; i < s.size(); ++i) {
      if (s[i] == ' ' && (--k) == 0) {
        return s.substr(0, i);
      }
    }
    return s;
  }
};

```

### Python

```python
class Solution:
    def truncateSentence(
        self, s: str, k: int) -> str: return ' ' . join(s . split()[: k])

```