How many valid JSON strings are there?

18 min read Original article ↗

How many valid JSON strings are there?

A valid JSON string is a string conforming to the simple grammar described at json.org.

In this scenario a string is a finite sequence of Unicode characters. Unicode provides us with an alphabet of some 1,114,112 possible characters, which we number in hexadecimal from U+0000 to U+10FFFF inclusive.

These characters originate in Unicode, but aside from serving as a basic lookup table — character U+0020 is a space, for example, and x is U+0078 — Unicode itself is not actually massively important to this question. The JSON grammar doesn't say anything about the use or misuse of reserved Unicode characters, the proper matching of surrogate pairs or anything like that. This makes our job a lot easier.

The various possible binary encodings of a Unicode string, such as UTF-8, are also not considered here. String length will be measured in characters, not in bytes. This also simplifies things.

There are 1,114,112N possible strings of length N ≥ 0, but not all of these are valid JSON. For example, there is only one string of length N = 0, '', but this is not valid JSON. There are 1,114,112 strings of length N = 1, only 10 of which are valid JSON: the single digits, '0' to '9'.

Some valid JSON strings for N = 4 would be 'null', 'true', '1234', '"ab"' and '[{}]'. There are many others. There are 10 × 10 × 10 × 10 = 10,000 strings which take the form of four digits but only 9,000 of these are valid JSON; JSON allows a lone '0', but disallows leading zeroes, such as in '0123'. "Stringified strings", of the form '"ab"' — double quote, character, character, double quote — allow over a million possibilities for each of the two characters, resulting in over a trillion possible combinations. These make up the vast majority of the possibilities when N ≥ 3.

JSON strings may also feature whitespace. There are four permissible whitespace characters. This means that there are some 16 possible strings of the form ' {} ' — that is, whitespace, left brace, right brace, whitespace — and 1,024 of the form ' [ { } ] ', and so on. We will therefore draw a distinction between a JSON value and a JSON element:

  • A value always starts and ends with a non-whitespace character. 'true', '[      ]' and '123.4567e+89' are all values.
  • An element may (or may not) be padded at the beginning and end with whitespace. All values are elements. Examples of elements which are not values are '19 ' and ' {} '. It's the enumeration of all possible elements which we care about.

(Later, we'll find out what happens if we disallow whitespace.)

Table of values

N Number of valid JSON strings of length N
00
110
2183
31,116,690
41,241,178,737,201
51,382,769,886,828,373,987
61,540,513,509,987,425,647,994,799
71,716,252,210,190,833,344,214,413,058,975
81,912,038,829,837,307,338,535,532,996,384,125,503
92,130,160,395,481,217,702,782,516,195,462,638,598,742,492
102,373,164,833,092,220,366,519,238,536,719,956,333,503,580,977,677

A table of values up to N = 100 is here.

I've gone as far as N = 350 working locally. The calculation gets progressively slower as the numbers involved rise into the thousands of digits; the only real constraint on how far we can go is patience.

Specifics of the enumeration process

'null', 'true' and 'false' are all fixed-length tokens which are very easy to check for.

As mentioned, there are four possible whitespace characters. These are the space (U+0020), tab (U+0009), carriage return (U+000D) and line feed (U+000A). If there are N characters of whitespace, then we multiply the number of possibilities by 4N.

JSON numbers have several different formats. I found that the least confusing approach was to enumerate numbers of the form 123, 123.456, 123e456 and 123.456e789 separately. There are six different permitted exponent symbols: E, e, E+, e+, E- and e-. As these have differing lengths, the enumeration becomes more complicated. Leading zeroes are not permitted, which makes the enumeration more complicated again. That said, all of these can still be enumerated using fairly simple closed form expressions.

The fact that a JSON consumer would almost certainly interpret the expressions 1e9 and 1E9 identically doesn't affect our calculation. These are distinct strings so we count them separately. The same applies to apparently identical numbers such as 1e+9, 10E8, 1000000000.000000000 and so on.

The possibility of a leading unary minus sign doesn't make any of this significantly more complicated. JSON does permit '-0' but again, we don't care whether or not a JSON consumer would interpret this differently from '0'.

JSON strings — that is, stringified strings, the results you get from doing something like JSON.stringify('abc'), which results in the five-character string '"abc"' — are more complicated. The string "interior", between the two double quotes, consists of three different types of character:

  • Valid single characters are those from U+0020 to U+10FFFF inclusive, except for the double quote " and the backslash \. There are 1,114,078 of these.

  • There are also 8 simple backslash escape sequences. Each is 2 characters long, consisting of a backslash \ followed by one of eight possible characters: ", /, \, b, f, n, r or t. For example, \n. What these escape sequences actually mean/do is actually not important for this piece of work.

  • Lastly there are hex escapes. These are 6 characters long, consisting of a backslash \, a u and 4 hexadecimal digits. For example, \u0020. As the hexadecimal digits are not case-sensitive, there are not 16 but 22 possible hexadecimal digits, and not 164 = 65,536 but 224 = 234,256 possible hex escape sequences. Again, these create distinct strings so we count them all, even if a consumer would almost certainly treat \uffff and \uFFFF identically.

Putting it all together, we develop a fairly simple Fibonacci-esque recurrence relation for the number of possible string interiors of length N:

a0 = 1 a1 = 1114078a0 a2 = 8a0 + 1114078a1 a3 = 8a1 + 1114078a2 a4 = 8a2 + 1114078a3 a5 = 8a3 + 1114078a4 aN = 234256aN-6 + 8aN-2 + 1114078aN-1 (N≥6)

Or...

( aN-5 aN-4 aN-3 aN-2 aN-1 aN ) = ( 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 234256 0 0 0 8 1114078 ) N ( 0 0 0 0 0 1 )

Memoization makes this pretty fast to compute. The number of operations is O(N), though of course the time taken for each operation is not really constant.

I imagine that there is a closed-form solution possible here, akin to the one for the Fibonacci sequence but six to ten times more ghastly and complicated. Unlike the Fibonacci sequence, there is no closed-form solution for this recurrence relation; the polynomial in question is too complicated.

As for those other formats...

The smallest array is of course '[]' (N = 2) and the smallest object is '{}' (N = 2). The smallest non-empty array is of the form [0] (N = 3) and the smallest non-empty object is of the form '{"":0}' (N = 6) — there are 10 of each of these.

We do not care about duplicate keys in objects — JSON does not either. '{"":1,"":2}' (N = 11) is valid JSON. Exactly how this should be interpreted, or even whether this is an error, is unspecified. The merit of this is debated but for this specific piece of work this is good because it would make the job unbelievably harder otherwise. (For an example of how omissions in the JSON specification can be exploited to increase parsing and serialisation performance, check out my fastjson project.)

Beyond this point, I think the simplest explanation of what I did is just the code itself...

Code

Here!

At present I do not have code to actually generate the distinct JSON strings in question. This would be doable but I do note that as N increases past 3 the task of generating them all becomes deeply impractical. Some option for restricting the space of allowable single string characters might be useful here.

Observations

N = 0

There are 0 valid JSON strings of length 0. JSON.parse('') throws an exception.

N = 1

There are 10 valid JSON strings of length 1. These are the single digits '0' to '9'.

Note that none of these elements have padding — they are all values as well as being elements.

N = 2

There are 183 valid JSON strings of length 2. 103 of these are values, which is to say they have no whitespace padding:

  • '{}', '[]' and '""' (3)
  • Numbers '10' to '99' (90)
  • Numbers '-0' to '-9' (10)

The remaining 80 are the 10 values of length 1 padded with one space on either side. Let s represent a whitespace character:

  • '0s' through '9s' (10 × 4 = 40)
  • 's0' through 's9' (4 × 10 = 40)

N = 3

There are 1,116,690 valid JSON strings of length 3. 1,304 of these are smaller strings padded with space:

  • The 10 values of length 1, padded to length 3:

    • 'Xss' (10 × 4 × 4 = 160)
    • 'sXs' (4 × 10 × 4 = 160)
    • 'ssX' (4 × 4 × 10 = 160)

  • The 103 values of length 2, padded to length 3:

    • 'XXs' (103 × 4 = 412)
    • 'sXX' (4 × 103 = 412)

The remaining 1,115,386 are values of length 3:

  • 1,114,078 strings of the form '"x"'
  • 900 numbers of the form '123' (again, remember leading zeroes are not permitted)
  • 100 numbers of the form '1.2'
  • 200 numbers of the form '1e2' or '1E2'
  • 90 numbers of the form '-12'
  • 10 arrays of the form '[4]'
  • 4 arrays of the form '[ ]' (remember, there are four possible whitespace characters)
  • 4 objects of the form '{ }'

N = 4

There are 1,241,178,737,201 valid JSON strings of length 4. 8,930,592 of these are smaller strings padded with space:

  • The 10 values of length 1, padded to length 4:

    • 'Xsss' (10 × 4 × 4 × 4 = 640)
    • 'sXss' (4 × 10 × 4 × 4 = 640)
    • 'ssXs' (4 × 4 × 10 × 4 = 640)
    • 'sssX' (4 × 4 × 4 × 10 = 640)

  • The 103 values of length 2, padded to length 4:

    • 'XXss' (103 × 4 × 4 = 1,648)
    • 'sXXs' (4 × 103 × 4 = 1,648)
    • 'ssXX' (4 × 4 × 103 = 1,648)

  • The 1,115,386 values of length 3, padded to length 4:

    • 'XXXs' (1,115,386 × 4 = 4,461,544)
    • 'sXXX' (4 × 1,115,386 = 4,461,544)

The remaining 1,241,169,806,609 are values of length 4:

  • 1,241,169,790,092 are "stringified strings", of which:

    • 1,114,0782 = 1,241,169,790,084 are of the form '"ab"' where a and b are each single characters
    • 8 are 2-character escapes of the form '"\\n"'

  • 16,517 are not strings:

    • 16,300 are numbers:

      • 9,000 numbers of the form '1234'
      • 1,900 numbers of the form '1.23' or '12.3'
      • 3,800 numbers of the form '1e23', '1E23', '12e3' or '12E3'
      • 400 numbers of the form '1e+2', '1E+2', '1e-2' or '1E-2'
      • 900 numbers of the form '-123'
      • 100 numbers of the form '-1.2'
      • 200 numbers of the form '-1e2' or '-1E2'

    • 199 are arrays:

      • 16 empty arrays of the form '[  ]'
      • 183 arrays with a single entry, of the form '[XX]' - see the result for N = 2, above
    • 16 are objects (all empty, of the form '{  }')
    • and 1 is 'null'!
    • and 1 is 'true'!

It should now be clear that the stringified strings are going to dominate these figures going forward.

Higher N

'false', the last fixed token, first appears at N = 5, naturally. This is also where we first encounter arrays with multiple entries such as '[1,2]' and numbers with both a decimal and an exponent such as '1.2E9'.

Our first non-empty objects, of which there are 10 of the form '{"":0}', appear at N = 6. Here we also start seeing numbers with both a decimal and a signed exponent, such as '9.9e-9'.

As N increases, the vast majority of JSON strings take the form of stringified strings and the vast majority of these in turn consist exclusively of single characters (not escape sequences). That is, JSON of the form '"abc..."'. There are 1,114,078N - 2 possible valid JSON strings of this form, easily exceeding all other partially escaped strings, let alone formats such as arrays and objects. In fact, 1,114,078N - 2 is a very reasonable approximation for the number of valid JSON strings of length N ≥ 3.

What if we disallow whitespace?

Well, here's the table:

N Number of valid JSON strings of length N, disallowing whitespace
00
110
2103
31,115,378
41,241,169,806,497
51,382,759,957,416,341,979
61,540,502,447,848,189,871,865,303
71,716,239,886,104,877,753,069,071,001,039
81,912,025,099,844,274,016,966,438,855,135,598,311
92,130,145,099,198,039,027,362,775,288,519,180,372,992,548
102,373,147,791,839,649,124,325,020,160,021,655,103,136,553,007,029

A table of values up to N = 100 is here.

The approximation of 1,114,078N - 2 remains accurate. The figures for N = 0 and N = 1 are the same as whitespace does not factor into those figures. Beyond this point, we find that there is no distinction between values and elements, and our calculations are a little simpler because we no longer need to count whitespaced elements from prior N:

N = 2

There are 103 valid JSON strings of length 2, disallowing whitespace:

  • '{}', '[]' and '""' (3)
  • Numbers '10' to '99' (90)
  • Numbers '-0' to '-9' (10)

N = 3

There are 1,115,378 valid JSON strings of length 3, disallowing whitespace:

  • 1,114,078 strings of the form '"x"'
  • 900 numbers of the form '123'
  • 100 numbers of the form '1.2'
  • 200 numbers of the form '1e2' or '1E2'
  • 90 numbers of the form '-12'
  • 10 arrays of the form '[4]'
  • 0 arrays of the form '[ ]' (remember, whitespace is disallowed)
  • 0 objects of the form '{ }'

N = 4

There are 1,241,169,806,497 valid JSON strings of length 4, disallowing whitespace:

  • 1,241,169,790,092 are "stringified strings", of which:

    • 1,114,0782 = 1,241,169,790,084 are of the form '"ab"' where a and b are each single characters
    • 8 are 2-character escapes of the form '"\\n"'

  • 16,405 are not strings:

    • 16,300 are numbers:

      • 9,000 numbers of the form '1234'
      • 1,900 numbers of the form '1.23' or '12.3'
      • 3,800 numbers of the form '1e23', '1E23', '12e3' or '12E3'
      • 400 numbers of the form '1e+2', '1E+2', '1e-2' or '1E-2'
      • 900 numbers of the form '-123'
      • 100 numbers of the form '-1.2'
      • 200 numbers of the form '-1e2' or '-1E2'
    • 103 are arrays with a single entry of the form '[XX]' - see the result for N = 2, above
    • 0 are objects (again, '{  }' is disallowed)
    • and 1 is 'null'!
    • and 1 is 'true'!

An incomplete list of things which are not valid JSON

  • Leading zeroes e.g. '0451'
  • Omitted leading digit on a decimal e.g. '.123'
  • Omitted trailing digits after a decimal e.g. '456.'
  • Unary plus sign at the start of a number e.g. '+7800'
  • Hexadecimal, octal or binary numeric literals such as '0x10FFFF', '0o755' or '0b11001010'
  • Other JavaScript-style string escape sequences such as '\\v', '\\x45', '\\u{10FFFF}' (no, you can't hex-escape characters beyond U+FFFF at all, you just have to put them in the string as literals)
  • Trailing commas in arrays or objects

Note that for the purposes of this piece of work, most of these omissions make the counting a lot easier.

Discussion (10)

2025-09-24 00:24:13 by Mr.E:

Nice writeup. I had forgotten about fastjson, that one took me a while to figure out again.

2025-09-24 02:41:20 by wuweiwolf:

The sequence of the number of string interiors should be expressible in terms of the 6 roots of the polynomial x^6 - 1114078 x^5 - 8 x^4 - 234256, and would have the same general form as the Fibonacci formula, i.e. the n-th string interior number would be a weighted sum of each of those roots raised to the n-th power. Though the weights would probably look quite complicated. However, for polynomials of degree 5 or larger, there is no closed form expression for the roots themselves (i.e. there is no quintic, or in this case sextic, formula). I checked this polynomial using Sage (basically just copying the code here: https://math.stackexchange.com/a/4003413), and it is not one of the solvable cases. So unless you define "closed form" to include generic polynomial roots, there is no closed-form expression for the number of string interiors of length n.

2025-09-24 02:53:30 by wuweiwolf:

Oh, also, although there's no exact closed form, numerically it seems that the largest-magnitude root of the polynomial is within 10^-5 of 1114078. This just reflects the fact that once n is large enough, the n-th number is pretty well approximated by just multiplying the (n-1)-th number by 1114078.

2025-09-24 04:54:32 by trillian:

Regarding the polynomial x^6 - 1114078 x^5 - 8 x^4 - 234256 mentioned by wuweiwolf: there's a trick here that's analogous to a property of the Fibonacci closed form formula. Namely, while the exact formula is of the form (phi^n + psi^n)/sqrt(5), one can actually ignore the psi^n term for large enough n, since its magnitude is smaller than 1, and instead round to the nearest integer. It turns out that "large enough n" is actually "n ≥ 0". One can apply the same trick here: of the 6 roots, one has magnitude ≈1114078, and the other 5 have magnitude ≈0.73207. In addition, the constant coefficient of the large root is very close to 1 (about 1 - 6.45e-12) and the coefficients for the other roots are all around 1.31e-7. So, a "closed form" for the sequence is round(c * a^n), with a being the large root of the polynomial and c being its constant term. I agree that c is not easy to compute though :), it involves solving a 6x6 matrix of degree-6 algebraic numbers. While Sage can compute it to acceptable precision, it hangs if I ask if what the degree of it is.

2025-09-25 23:10:35 by Wyatt S Carpenter:

An interesting read as usual, qntm! I don't think your convention here of representing the json strings by the way you would write that string value in JavaScript is very helpful. Since you already have the different backgrounds for the code type words (and also it's pretty obvious from context), you should just rely on that for the strings as you did for the individual characters/values. > 8 are 2-character escapes of the form '"\\n"' This is not very smooth reading, for example 😉

2025-09-26 16:45:45 by qntm:

No, it's better this way because it's clearer for strings with quotes in, strings which start or end with whitespace, and the empty string.

2025-10-03 12:24:10 by Matt:

> Memoization makes this pretty fast to compute. The number of operations is O(N). Maybe this is what you meant, but I believe going from a_(N-1) to a_N is O(N) and calculating a_n from scratch is O(n^2) because it's true that it's O(N) generic math operations, but those math operations are on exponentially growing numbers so unless there's a way to do the multiplication outside of naive arithmetic you'll end up needing to do O(N) operations on the bounded size integers that are used to represent the arbitrarily large integers. The super-linear growth is pretty obvious when looking at the runtimes of my most obvious memoization or dynamic programming implementations in python. Doubling n roughly quadruples the runtime, as I'd expect for quadratic growth. import timeit import sys def dp_a_n(n): twoBefore = 0 oneBefore = 1 if n == 0: return 1 current = None for i in range(n): current = 1114078*oneBefore + 8*twoBefore twoBefore = oneBefore oneBefore = current return current for i in range(15): n= 2**i duration = timeit.timeit(lambda: dp_a_n(n), number=100) print(n, duration) outputs ... 64 0.0006055999983800575 128 0.001975200000742916 256 0.0068241999979363754 512 0.0237693999952171 1024 0.08607349999510916 2048 0.30920760000299197 4096 1.1863041999968118 8192 4.8013875000033295 16384 18.96822930000053 My memoization implementation produces similar results, but can't go to as high of an n due to recursion limits import sys sys.setrecursionlimit(2100) def memo_a_n(n): mem = {0: 1, 1: 1114078} def _helper(n, memo): if n in memo: return memo[n] result = 1114078*_helper(n-1, memo) + 8*_helper(n-2, memo) memo[n] = result return result return _helper(n, mem) for i in range(12): n= 2**i duration = timeit.timeit(lambda: memo_a_n(n), number=100) print(n, duration) outputs ... 64 0.0013360000011743978 128 0.0039986999981920235 256 0.01196909999998752 512 0.03522099999827333 1024 0.11080910000600852 2048 0.4737251999977161

2025-10-03 21:44:16 by qntm:

Yes, the number of operations is O(n) but the time taken to execute each operation is not constant, I was hoping I wouldn't need to make that explicit but I guess here we are...

2025-10-21 22:18:22 by Incompleteusern:

I don't think this has been noted yet, but as noted by https://en.wikipedia.org/wiki/Fibonacci_sequence#Matrix_form for the Fibonacci sequence, we may find an in O(log n) operations by taking the corresponding 6 by 6 matrix for our recurrence relation here, and using exponentiation it by squaring.