Length of String 3

The previous string-length challenge capped out at 999 characters. This one wants a million.

Once more, LengthOfString<S> works like Array#length:

[object Object]

Differing from the two previous challenges about strings' length, this time the type must support strings about $10^6$ characters long. Even a perfectly tail-recursive one-character-at-a-time loop caps out at 1000 iterations, so this challenge forces a genuinely new idea: processing the string in large batches and assembling the count digit by digit.

Detailed Explanation

The solution, in full:

// Composable chunk patterns: each level is ten copies of the previous one,
// so P100K is a template literal pattern of 100,000 single-character slots.
// The `& {}` stops TypeScript from collapsing the all-string template
// back into plain `string`.
type P1 = string
type P10 = `${P1}${P1}${P1}${P1}${P1}${P1}${P1}${P1}${P1}${P1 & {}}`
type P100 = `${P10}${P10}${P10}${P10}${P10}${P10}${P10}${P10}${P10}${P10}`
type P1K = `${P100}${P100}${P100}${P100}${P100}${P100}${P100}${P100}${P100}${P100}`
type P10K = `${P1K}${P1K}${P1K}${P1K}${P1K}${P1K}${P1K}${P1K}${P1K}${P1K}`
type P100K = `${P10K}${P10K}${P10K}${P10K}${P10K}${P10K}${P10K}${P10K}${P10K}${P10K}`
 
// Strips as many copies of Chunk as possible from the front of S,
// returning [howMany, remainder]. A single pattern match consumes an
// entire chunk, so even million-character strings need only a few steps.
type CountChunks<
  S extends string,
  Chunk extends string,
  N extends 1[] = [],
> = S extends `${Chunk}${infer Rest}`
  ? CountChunks<Rest, Chunk, [...N, 1]>
  : [N['length'], S]
 
// Converts the concatenated digit string to a number,
// trimming leading zeros ('' parses to 0).
type ToInt<S extends string> = S extends `0${infer Rest}`
  ? ToInt<Rest>
  : S extends `${infer N extends number}`
    ? N
    : 0
 
// Count 100K-blocks first (unbounded, so it also covers the millions),
// then 10K, 1K, 100, 10 and single characters, like reading off the
// decimal digits of the length from most to least significant.
type LengthOfString<S extends string> =
  CountChunks<S, P100K> extends [infer D5 extends number, infer R5 extends string]
    ? CountChunks<R5, P10K> extends [infer D4 extends number, infer R4 extends string]
      ? CountChunks<R4, P1K> extends [infer D3 extends number, infer R3 extends string]
        ? CountChunks<R3, P100> extends [infer D2 extends number, infer R2 extends string]
          ? CountChunks<R2, P10> extends [infer D1 extends number, infer R1 extends string]
            ? CountChunks<R1, P1> extends [infer D0 extends number, string]
              ? ToInt<`${D5}${D4}${D3}${D2}${D1}${D0}`>
              : never
            : never
          : never
        : never
      : never
    : never

It looks like a lot. Underneath are three ideas: patterns that compose, a counter that strips whole chunks per match, and a digit readout at the end.

Why counting one character at a time can't work

The natural instinct is to reuse the Length of String 2 solution: peel one character per step, push a marker into an accumulator tuple, and return the tuple's length. That approach hits three separate walls here:

• The tail-recursion cap. TypeScript evaluates tail-recursive conditional types as a loop, but that loop is limited to 1000 iterations. One character per iteration tops out at 999.
• The tuple cap. Even if the loop could run longer, tuple types max out around 10,000 elements. An accumulator can never represent a length in the millions.
• Quadratic work. Suppose both limits vanished. Every match of `${string}${infer Rest}` materializes Rest as a brand-new string type that's almost as long as the input. On an 8.4-million-character string, that's 8.4 million matches, each building a multi-megabyte intermediate type. No amount of patience survives that.

The only way out is to make each pattern match do vastly more work: consume many characters at once.

Patterns compose: from one slot to 100,000

You already know the key inference rule: in a template literal pattern, every placeholder that has something after it matches exactly one character. So far you've used that with infer to capture a character. The new move is to use it without infer, purely to build fixed-width patterns, and to notice that such patterns compose:

type P1 = string // one slot = exactly 1 character (when not final)
type P10 = `${P1}${P1}...${P1 & {}}` // ten slots = exactly 10 characters
type P100 = `${P10}${P10}...${P10}` // ten P10s = exactly 100 characters

Each level is just ten copies of the previous one, so five short aliases take us from 1 to 100,000 characters. The pattern width grows exponentially while the code grows linearly. P100K is, after expansion, a single template literal pattern with 100,000 one-character slots.

The one subtlety is the ${P1 & {}} in P10. A template literal type built purely out of string holes carries no information TypeScript cares to keep; it would normalize `${string}${string}...${string}` right back to plain string. If that happened, P10 (and everything built on it) would lose its "exactly N characters" meaning: a plain string hole in a non-final pattern position consumes exactly one character, not ten thousand. Intersecting one hole with {} produces string & {}, which is assignable the same way but is not syntactically string, so the template survives normalization. It's only needed once, in P10. Every higher level is built from P10 and inherits the non-collapsed structure.

CountChunks: strip a whole block per match

CountChunks<S, Chunk> repeatedly asks one question: does S start with Chunk?

[object Object]

When Chunk is P100K, this is a single pattern match whose first 100,000 slots each consume exactly one character and whose final infer Rest captures everything after them. Each successful match adds one element to the tuple counter N and recurses on Rest; the first failed match returns [N['length'], S], meaning how many chunks fit and what was left over.

That completely changes the arithmetic. An 8,464,592-character string (the largest test case) needs just 84 successful matches at the P100K level, plus one failing match to detect the end, instead of 8.4 million single-character steps. The recursion is tail-recursive with double-digit iteration counts, comfortably inside every limit.

The digit cascade

LengthOfString runs CountChunks six times, from the biggest chunk to the smallest, always on the previous level's remainder:

// S has 8,464,592 characters
// CountChunks<S,  P100K> → [84, <64,592 chars>]   D5 = 84
// CountChunks<R5, P10K>  → [6,  <4,592 chars>]    D4 = 6
// CountChunks<R4, P1K>   → [4,  <592 chars>]      D3 = 4
// CountChunks<R3, P100>  → [5,  <92 chars>]       D2 = 5
// CountChunks<R2, P10>   → [9,  <2 chars>]        D1 = 9
// CountChunks<R1, P1>    → [2,  '']               D0 = 2

Because each chunk is exactly ten times the next smaller one, every remainder is smaller than the chunk that produced it. From D4 down, each count is guaranteed to be a single digit from 0 to 9. Those counts are the decimal digits of the length, read most-significant-first: there is no type-level addition or multiplication anywhere in this solution, place value does the arithmetic for us. Only the top-level D5 is unbounded, and that turns out to be a feature; we'll come back to it. (The last level can discard its remainder with a bare string, since P1 peels every remaining character and always leaves ''.)

One note about the pile of : never branches in LengthOfString: they can never actually fire, because CountChunks always returns a [count, remainder] pair. The extends [infer ...] checks are just the syntax for destructuring that pair, and a conditional type's false branch is mandatory; never is the conventional filler.

Gluing the counts together as text gives `${84}${6}${4}${5}${9}${2}` = '8464592', and ToInt finishes the job: it recursively trims leading '0's, then converts the digit string to an actual number literal with `${infer N extends number}`, the same infer ... extends trick from the String to Number challenge. Anything that doesn't parse as a number falls through to 0.

Edge cases the tests cover

• LengthOfString<''> → 0: every count is zero, giving '000000'. Trimming removes all of it, and the empty string doesn't match `${infer N extends number}`. That is what the : 0 fallback in ToInt is for.
• Lengths like 58901 with high-order zeros: the raw digit string is '058901'. Trimming strips exactly the leading zero while the interior zero survives, because ToInt stops recursing at the first non-zero character.
• Lengths past a million, like 8464592: D5 comes back as the two-digit count 84, which contributes two leading digits to the concatenation. Since only the first count may exceed 9, no padding logic is needed anywhere.

A note on performance

This is the part that makes the challenge hard. The test suite generates strings up to 8.4 million characters, and at that scale the type checker's costs become very real: a solution that peels small pieces off multi-megabyte string types over and over doesn't fail with an error, it freezes your editor. The pattern-composition approach does the same job in roughly a hundred pattern matches total across all six levels, and the entire 20-case suite checks in about 18 seconds.

The lesson travels well beyond this puzzle. Template literal patterns compose, so a handful of aliases can encode "exactly 100,000 characters". Counting batches at several scales and reading the batch counts as digits is the type-level version of positional notation itself. Whenever a recursion limit stands between you and a big input, make each step exponentially bigger instead of taking more steps.