https://leetcode.com/problems/encode-and-decode-strings/

I was asked this in an interview – don’t remember the company now, but I do remember struggling to solve it 🙂

If you cheat – this becomes a very easy problem to solve. By cheat I mean you could just use a character not present in the standard 256 ASCII list as your ‘marker’. To decode, you could just split the string (swift string.split weirdly filters out empty strings – which fails the test cases set for this problem. So instead we have to iterate and match each character to the ‘marker’) by using the marker and you would get back the original string. Most interviewers would not accept the solution – simply saying what if we wanted to extend the support to other characters in the future?

So to make the solution more generalized, we have to come up with a better strategy. Leetcode’s solution set covers some of them.

The strategy I used, encodes the string by writing its length along with a marker before the actual string e.g. hello would be encoded as “#5#hello”. While decoding, I wait for “#” to be read – after that I try to read a number till I find the next “#” – once I know the length of the upcoming string – reading that string becomes fairly straightforward.

In my first attempt I tried to encode using the pattern “#5hello” -> but this breaks for strings that start with a number e.g. 1word -> this would be encoded as #51word -> this breaks the decoding since we could not infer correctly if the upcoming string is of length 5 or 51. But using #length#string pattern fixes that issue.