Why not just join the strings with a delimiter?

Any delimiter character can also appear inside a word, so splitting on it breaks those words apart. A length prefix avoids the problem: the decoder reads the length, then takes exactly that many characters, without looking inside them.

What if a word contains '#' or digits?

It does not matter. The decoder only searches for '#' between records, starting at a record's first character, where the length digits are. Inside the word it counts characters instead of searching, so '#' and digits there are just data.

What is the time complexity?

O(n) for both encode and decode, where n is the total number of characters. Each character is written once and read once.

Encode and Decode Strings

Encode a list of strings into one string and decode it back with length prefixes, read by two pointers.

MediumSolve on LeetCode

Problem Understanding

Encode and Decode Strings: design encode, which turns a list of strings into a single string, and decode, which turns that string back into the original list. Words may contain any character, including whatever you would like to use as a separator.

Example: ["neet", "code", "love", "you"] encodes to "4#neet4#code4#love3#you" and decodes back to the same list.

Attempt 1: Join With a Delimiter

Joining with , and splitting on , fails as soon as a word contains a comma. Escaping the delimiter works, but it means rewriting every word and carefully undoing it. A length prefix needs neither.

The Intuition: Say How Long Each Word Is

Write each word as <length>#<word>. To decode, use two pointers:

i sits at the start of a record. Move j forward from i to the first #: the characters between are the length.
Take exactly length characters after the #: that is the word, whatever it contains.
Set i to the character after the word and repeat.

The # search only ever runs over the length digits, never inside a word, so a # in the data cannot confuse it.

Interactive Walkthrough

First each word is appended as length#word. Then the decoder walks the string: i marks a record's start, j its #, the length digits fill in, and the word after the # is taken by counting.

Dry Run Table

Decode: "3#a#b0#1#c"

`i`	`j` (first `#`)	Length	Word	Next `i`
0	1	3	`a#b`	5
5	6	0	`""`	7
7	8	1	`c`	10

The # at index 3 is inside the first word and is never searched for.

The Solution Template

Length-prefixed encoding, decoded with two pointers.

Encode and Decode Strings Code

1const encode = (strs) => strs.map((s) => `${s.length}#${s}`).join('');
2
3const decode = (s) => {
4    const out = [];
5    let i = 0;
6    while (i < s.length) {
7        const j = s.indexOf('#', i);
8        const length = Number(s.slice(i, j));
9        out.push(s.slice(j + 1, j + 1 + length));
10        i = j + 1 + length;
11    }
12    return out;
13};

Edge Cases & Common Mistakes

Empty strings: encode to 0#; decode takes zero characters and moves on.
Words containing # or digits: handled, because the decoder counts characters inside a word instead of searching.
Lengths with several digits: j scans to the #, so 12#... reads as twelve, not one.
Searching for # from the start of the string each time: always start from i, or the first record's # is found again.

Summary

Prefix every word with its length and a #. Decoding is a two-pointer walk: j finds the # that ends the length, and i jumps over exactly that many characters. Counting instead of searching is what makes any character safe inside a word.

More practice: DSA interview questions with answers · patterns cheat sheet

Palindromic Substrings

Container With Most Water