beraliv

Length of String

Example of LengthOfString use
Example of LengthOfString use

Today we discuss LengthOfString

Sounds easy but can be tricky. Let's find out ⬇️

Iterate over the string

First things first, we iterate over the string, right? 🧐

Iteration over the string
Iteration over the string

But construction L + 1 is not valid in TypeScript 😔 Check it yourself in https://tsplay.dev/N9AMoN

So now we need to have an array of numbers. We can go to the browser or node CLI, call this JS chunk and generate an array of 100 numbers for the start:

Generate Array of 100 elements from 0 to 99
Generate Array of 100 elements from 0 to 99

Now instead adding 1 to the previous length, we shift the array (or remove the first element from the array):

Shift array on every character
Shift array on every character

But now at the end of iteration we will get an array, but not the number. The only change which is required now is to extract the length. As we started the array from 0, the answer will be the first element:

Solution, version 1
Solution, version 1

Check that it's working – https://tsplay.dev/mMy2km 🔥

Maximum string length

If you check which string has the maximum possible length at the moment, it's 43. After this length, we will get Type instantiation is excessively deep and possibly infinite – https://tsplay.dev/w62orw

We have a limit of 43 recursive calls.

Can we do better? Of course, but this requires a better iteration. Is it even possible? Sure 🚀

Let's first try to iterate over 2 characters at one time if possible. Otherwise use one:

First check 2 characters if possible
First check 2 characters if possible

Now the maximum number is almost increased by a factor of two: it's 85 – https://tsplay.dev/WoqppN

Can we still do better? Sure, but then we need to have a larger array (100 is not enough). Also, let's iterate over 4 characters at one time:

First check 4 characters if possible
First check 4 characters if possible

Now the number is 163 – https://tsplay.dev/wRp3Em

Do you see the consequence? We iterate over the power of 2 number of characters. Why do we do so? To increase the limit twofold in comparison to the previous solution (but it's not actually 2x, as Shift calls make it more slow)

What will be the limit if we continue to do so? Let's see the table for the dependency:

Max charactersMax lengthImprovement
143-
285+97.67%
4163+91.76%
8295+80.98%
16463+56.95%
32415-10.37%

From left to right we see the maximum number of characters at one iteration, maximum length of string and improvement in comparison to the previous solution.

So I decided to stop on 463 😅 https://tsplay.dev/NVn1xN

Can you do better?

typescript
Alexey Berezin profile image

Written by Alexey Berezin who loves London 🏴󠁧󠁢󠁥󠁮󠁧󠁿, players ⏯ and TypeScript Follow me on Twitter