Trail Guide Snippets

Easysliding windowAlso known as Overlapping Text Chunking

A hiking club is loading its trail guide into a question-answering assistant. The assistant cannot read the whole guide for every question, so the guide is cut into short snippets. Only the few snippets that best match a question are handed to the model.

If you cut cleanly every 50 words, a sentence like "after the bridge, turn left at the cairn" can be split across two snippets, and neither one makes sense alone. So each snippet repeats the last few words of the one before it. This is how retrieval systems prepare documents before they are searched.

Your task

Write makeChunks(text, size, overlap). The words of text are separated by single spaces. Return a list of chunks, each chunk being words joined by single spaces:

The first chunk is words 0 to size - 1.
Each next chunk starts size - overlap words after the previous one and holds up to size words.
Stop after the first chunk that includes the last word. The last chunk may be shorter than size.

If text is the empty string, return an empty list.

makeChunks(text: string, size: int, overlap: int) → string[]

Examples

Example 1

Input

text = "cross the bridge then turn left at the cairn"
size = 4
overlap = 1

Output

["cross the bridge then", "then turn left at", "at the cairn"]

Why

There are 9 words and each chunk starts 4 - 1 = 3 words after the last. Chunks start at words 0, 3 and 6. The chunk starting at word 6 ("at the cairn") already includes the last word, so you stop there.

Example 2

Input

text = "fill water here the next tap is far"
size = 4
overlap = 2

Output

["fill water here the", "here the next tap", "next tap is far"]

Why

8 words, step 2. Chunks start at words 0, 2 and 4. The chunk at 4 ("next tap is far") ends exactly on the last word, so stop. A chunk starting at word 6 ("is far") would only repeat words you already have.

Example 3

Input

text = "steep path"
size = 5
overlap = 2

Output

["steep path"]

Why

Only 2 words, fewer than the chunk size, so the whole text is one chunk.

Constraints

0 ≤ number of words ≤ 10,000
1 ≤ size ≤ 1,000
0 ≤ overlap < size
text has no leading, trailing or double spaces.

Start with brute force

The obvious loop is "start at 0, keep stepping while start is less than the number of words". It is fast, but wrong: it keeps going after a chunk has already reached the end and adds small tail chunks that are completely contained in the previous one. Those duplicates waste space in the search index and can crowd out useful snippets.

The other common slip is stepping by size instead of size - overlap, which gives no overlap at all.

Hints

0 of 4 shown

Hint 1
In the first example, write out which word number each chunk starts at. How far apart are those starting points, and how does that relate to size and overlap?
Hint 2
Chunks start at 0, then every size - overlap words. With size 4 and overlap 1 that is 0, 3, 6, 9…
Hint 3
When do you stop? Look at the second example: a chunk starting at word 6 would fit inside the chunk before it. The rule is about whether a chunk has reached the end, not whether its start is still inside the text.
Hint 4
Split into words. Loop with start from 0 in steps of size - overlap. Take words[start : start + size], join it, add it, and break as soon as start + size ≥ number of words. Handle the empty text first.

Walkthrough and solution

Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.

How to solve it

Think of a window size words wide that slides along the text, size - overlap words at a time. The only subtle part is where to stop.

Trace "cross the bridge then turn left at the cairn" with size 4, overlap 1 (step 3, 9 words):

start 0: words 0 to 3, "cross the bridge then". 0 + 4 = 4 is less than 9, keep going.
start 3: words 3 to 6, "then turn left at". 3 + 4 = 7, keep going.
start 6: words 6 to 8, "at the cairn". 6 + 4 = 10 ≥ 9, so this chunk holds the last word. Stop.

Notice "then" appears in chunks 1 and 2, and "at" in chunks 2 and 3. That shared word is the overlap: anything near a boundary shows up whole in at least one chunk, as long as it is no longer than the overlap plus one word.

Reference solution

function makeChunks(text, size, overlap) {
  if (text === '') return [];
  const words = text.split(' ');
  const step = size - overlap;
  const chunks = [];
  for (let start = 0; ; start += step) {
    chunks.push(words.slice(start, start + size).join(' '));
    if (start + size >= words.length) break; // this chunk reached the last word
  }
  return chunks;
}

def make_chunks(text, size, overlap):
    if text == '':
        return []
    words = text.split(' ')
    step = size - overlap
    chunks = []
    start = 0
    while True:
        chunks.append(' '.join(words[start:start + size]))
        if start + size >= len(words):  # this chunk reached the last word
            break
        start += step
    return chunks

TimeO(c · size)There are c ≈ n / (size - overlap) chunks and each copies up to size words. With no overlap that is just O(n).

SpaceO(c · size)The output stores every chunk, so overlapping words are stored more than once.

Learn the idea: Chunking and Retrieval RAG Basics The Context Window

Ctrl+Enter runs

Run your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.

Write code