DSA-139 · Exact prefix decoding counts with one/two-digit token rules
Decode Ways
Intermediate · Java 21 · Version 1 · editorial draft
Java reference and baseline verified on JDK 21: 5485 deterministic checks. Learner drafts are not executed.
Understand the problem
Digits 1 through 26 encode letters A through Z. Given an ASCII digit string, return the number of complete valid decodings into those numbers. Tokens have one or two digits, and no token may begin with zero.
- digits is a non-null String of at most 10000 ASCII characters from 0 through 9. Null throws NullPointerException; longer input or any other character throws IllegalArgumentException. Unicode digit lookalikes and whitespace are rejected, and the complete string is validated before counting.
- Return an exact BigInteger without a modulus. Public empty input returns ZERO because the task requires a nonempty encoded message. For a nonempty message the internal empty-prefix count is ONE, the identity needed to extend a first valid token.
- A single 0 and any leading-zero message have zero decodings. Zero is legal only inside 10 or 20, not as its own token. Equal letter outputs are counted through valid tokenizations, and only the count is returned. The uncached recursive baseline is limited to short tests.
Examples
Input:
digits="12"
Output:21|2 gives AB, and 12 gives L.
Input:
digits="226"
Output:32|2|6, 22|6, and 2|26 are valid.
Input:
digits="11106"
Output:21|1|10|6 and 11|10|6 work; 0 cannot stand alone and 06 is invalid.
Input:
digits=""
Output:0The public empty-message result differs deliberately from the internal counting identity.
Before you start
- Disjoint final-token counting
- Zero handling and the difference between public empty input and internal empty prefix
Recognize the structure
A complete decoding ends with a valid one-digit token or a valid two-digit token. Removing that final token leaves the same prefix-count problem at length n−1 or n−2. Those families are disjoint by token width. The structure resembles Climbing Stairs, but token validity depends on actual digit values, so zeros and numbers above 26 can kill transitions.
Try before revealing
Hint 1
Classify complete tokenizations by the width of their final token.
Hint 2
What predecessor is used for a valid 10 pair, and why must the empty prefix contribute one?
Hint 3
Add old D(k−1) only for a nonzero last digit and old D(k−2) only for pairs 10..26.
Derive the solution
Reveal the baseline, optimized reasoning, and Java code
Enumerate valid next token widths recursively
At a suffix start, reject a leading zero. Otherwise recurse after one digit and optionally after two when their numeric value is at most 26. Reaching the end of a nonempty message contributes one completed tokenization. The public empty case is handled before this recursion. Repeated suffix starts cause exponential work, with O(2^n) upper-bound arithmetic operations and O(n+1) stack depth. Tests use independent cut masks, validating every resulting piece, and check a large all-ones count against Fibonacci fast doubling.
Improve the baseline
Define a prefix count with its exact bases
For nonempty input, D(k) counts tokenizations of the first k digits. D(0)=1 is the empty prefix available for extending a first token. D(1)=0 if the first digit is 0, otherwise one. Public empty input returns zero separately rather than corrupting this internal identity.
Classify the final token
For k≥2, add D(k−1) if the last digit is nonzero. Also add D(k−2) if the final pair has numeric value in 10..26. A pair such as 06 is six numerically but fails the lower bound ten, so it does not create a legal token. The two widths cannot describe the same tokenization.
Trace zeros rather than special-casing whole messages
For 101, D values are [1,1,1,1]: 10 uses the pair transition, and the final 1 extends that count. For 100, the last 0 has neither a one-digit token nor a valid 00 pair, so the final count is zero. A zero count naturally propagates impossible earlier prefixes.
Roll the two predecessor counts safely
Before length k, previousTwo=D(k−2) and previousOne=D(k−1). Begin next at ZERO and add only eligible predecessor counts. Compute both token contributions before shifting either register, then move previousTwo to old previousOne and previousOne to next.
Use exact arithmetic and a strict character contract
All-ones input follows D(k)=D(k−1)+D(k−2), so counts quickly exceed long. BigInteger preserves the exact value; immutable add results must be assigned. Direct comparisons with ASCII 0 and 9 enforce the stated encoding alphabet, rather than accepting unrelated Unicode numeric characters.
Why it is correct
Bases and public empty case
There is one way to extend an empty prefix before consuming a valid first token. A nonzero first digit has one decoding, and zero has none. Returning ZERO for an entirely empty public message is a separate API convention and does not alter the prefix induction.
Disjoint final-token recurrence
Every valid tokenization ends in one or two digits. Its final piece must satisfy exactly the corresponding validity test. Removing it gives a valid shorter-prefix tokenization, and appending it reverses the operation. Width distinguishes the two families, proving soundness, completeness, and no double counting.
Rolling invariant and termination
Both contributions read old predecessor values, so next equals D(k). Shifting afterward establishes the invariant for k+1. Increasing bounded lengths terminate, and the final register contains the full-message count. Exact BigInteger addition prevents overflow without weakening zero rules.
Complete Java reference and baseline
Save as Solution.java. Node definitions and imports are included where needed. The baseline is included for comparison; respect its input-size limits.
import java.math.BigInteger;
import java.util.Objects;
public final class Solution {
private Solution() {}
private static void validate(String digits) {
Objects.requireNonNull(digits, "digits");
if (digits.length() > 10_000) throw new IllegalArgumentException("too many digits");
for (int i = 0; i < digits.length(); i++) if (digits.charAt(i) < '0' || digits.charAt(i) > '9') throw new IllegalArgumentException("ASCII digits only");
}
public static BigInteger numDecodings(String digits) {
validate(digits);
if (digits.isEmpty()) return BigInteger.ZERO;
BigInteger previousTwo = BigInteger.ONE;
BigInteger previousOne = digits.charAt(0) == '0' ? BigInteger.ZERO : BigInteger.ONE;
for (int length = 2; length <= digits.length(); length++) {
BigInteger next = BigInteger.ZERO;
if (digits.charAt(length - 1) != '0') next = next.add(previousOne);
int pair = (digits.charAt(length - 2) - '0') * 10 + digits.charAt(length - 1) - '0';
if (pair >= 10 && pair <= 26) next = next.add(previousTwo);
previousTwo = previousOne;
previousOne = next;
}
return previousOne;
}
// Baseline: enumerate valid one/two-digit pieces; short inputs only.
public static BigInteger baseline(String digits) {
validate(digits);
return digits.isEmpty() ? BigInteger.ZERO : decode(digits, 0);
}
private static BigInteger decode(String digits, int start) {
if (start == digits.length()) return BigInteger.ONE;
if (digits.charAt(start) == '0') return BigInteger.ZERO;
BigInteger count = decode(digits, start + 1);
if (start + 1 < digits.length()) {
int pair = (digits.charAt(start) - '0') * 10 + digits.charAt(start + 1) - '0';
if (pair <= 26) count = count.add(decode(digits, start + 2));
}
return count;
}
}
Read the meaningful blocks
Validate before counting
The entire input is checked for ASCII digits and size before the empty branch or any leading-zero outcome. An invalid late character cannot be hidden by an already impossible prefix.
Initialize the identity and first-digit count
previousTwo starts at ONE, while previousOne reflects the actual first digit. These values represent different prefix lengths; setting both to ONE would accept a leading zero.
Add eligible tokens, then shift
The pair is built from two bounded digit values, so its int arithmetic is safe. Test 10≤pair≤26 independently of the one-digit rule, then preserve both old counts until next has received every contribution.
Complexity
For n code units and maximum count bit length B≥1, the reference performs O(n+1) validation/transition steps and O(n) BigInteger additions. Charging O(B) per addition gives O((n+1)(B+1)) time and O(B+1) live auxiliary bits plus a constant number of references. Since counts are bounded by Fibonacci growth, B=O(n+1); this is not constant memory in bits.
The uncached baseline has O(2^n(B+1)) upper-bound time and O((n+1)(B+1)) live storage including recursion and partial counts. Enumerating all decoded strings adds potentially exponential output costs. Trace prefix tables are explanatory histories and are not allocated by the two-register Java reference.
Exact-state walkthroughs
Reveal normal and boundary traces
Both final-token widths can contribute
Input: "226" · Exact valid decoding count: 3
Step 1 of 7: Seed the empty-prefix identity and the actual first-digit count.
D(0)=1 allows a first token to extend an empty prefix. A leading zero makes D(1)=0. All displayed counts are exact decimal strings.
Phase: initial.
ASCII digits: "226". Each token must be 1..26, with no leading zero.
Exact prefix counts — D(k) decodes the first k digits
- D(0)=1 — internal empty prefix
- D(1)=1
Live old predecessor pair
- previousTwo: 1
- previousOne: 1
Zero cannot stand alone. Pairs 10 and 20 are valid, while 06 and 00 are invalid. A zero prefix count means no complete tokenization reaches that boundary. Compute both old contributions before shifting; exact BigInteger values grow in bits.
All source values stay unchanged. Full grids, old layers and history cards explain state meaning; they do not add to Java reference workspace. Exact counts and products use decimal strings in trace data.
| Variable | Value |
|---|---|
| input | "226" |
| phase | "initial" |
| history | ["1","1"] |
| previousTwo | "1" |
| previousOne | "1" |
See the affected Java block
1 import java.math.BigInteger; 2 import java.util.Objects; 3 4 public final class Solution { 5 private Solution() {} 6 private static void validate(String digits) { 7 Objects.requireNonNull(digits, "digits"); 8 if (digits.length() > 10_000) throw new IllegalArgumentException("too many digits"); 9 for (int i = 0; i < digits.length(); i++) if (digits.charAt(i) < '0' || digits.charAt(i) > '9') throw new IllegalArgumentException("ASCII digits only"); 10 } 11 public static BigInteger numDecodings(String digits) { 12 validate(digits); 13 if (digits.isEmpty()) return BigInteger.ZERO; 14 BigInteger previousTwo = BigInteger.ONE; 15 BigInteger previousOne = digits.charAt(0) == '0' ? BigInteger.ZERO : BigInteger.ONE; 16 for (int length = 2; length <= digits.length(); length++) { 17 BigInteger next = BigInteger.ZERO; 18 if (digits.charAt(length - 1) != '0') next = next.add(previousOne); 19 int pair = (digits.charAt(length - 2) - '0') * 10 + digits.charAt(length - 1) - '0'; 20 if (pair >= 10 && pair <= 26) next = next.add(previousTwo); 21 previousTwo = previousOne; 22 previousOne = next; 23 } 24 return previousOne; 25 } 26 // Baseline: enumerate valid one/two-digit pieces; short inputs only. 27 public static BigInteger baseline(String digits) { 28 validate(digits); 29 return digits.isEmpty() ? BigInteger.ZERO : decode(digits, 0); 30 } 31 private static BigInteger decode(String digits, int start) { 32 if (start == digits.length()) return BigInteger.ONE; 33 if (digits.charAt(start) == '0') return BigInteger.ZERO; 34 BigInteger count = decode(digits, start + 1); 35 if (start + 1 < digits.length()) { 36 int pair = (digits.charAt(start) - '0') * 10 + digits.charAt(start + 1) - '0'; 37 if (pair <= 26) count = count.add(decode(digits, start + 2)); 38 } 39 return count; 40 } 41 } 42
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Seed the empty-prefix identity and the actual first-digit count.
D(0)=1 allows a first token to extend an empty prefix. A leading zero makes D(1)=0. All displayed counts are exact decimal strings.
- input
"226"- phase
"initial"- history
["1","1"]- previousTwo
"1"- previousOne
"1"
- Gate the two disjoint final-token families using old prefix counts.
A nonzero final digit may extend D(k−1). Only a pair in 10..26 may extend D(k−2); 06 is invalid even though its numeric value is six.
- input
"226"- phase
"candidate"- history
["1","1"]- previousTwo
"1"- previousOne
"1"- length
2- oneAllowed
true- pair
22- pairAllowed
true- oneContribution
"1"- twoContribution
"1"- next
"2"
- Shift only after both token contributions are known.
The live pair now describes D(k−1),D(k). Contribution cards preserve the old values actually used. Zero counts naturally propagate impossible prefixes.
- input
"226"- phase
"commit"- history
["1","1","2"]- previousTwo
"1"- previousOne
"2"- length
2- oneAllowed
true- pair
22- pairAllowed
true- oneContribution
"1"- twoContribution
"1"- next
"2"
- Gate the two disjoint final-token families using old prefix counts.
A nonzero final digit may extend D(k−1). Only a pair in 10..26 may extend D(k−2); 06 is invalid even though its numeric value is six.
- input
"226"- phase
"candidate"- history
["1","1","2"]- previousTwo
"1"- previousOne
"2"- length
3- oneAllowed
true- pair
26- pairAllowed
true- oneContribution
"2"- twoContribution
"1"- next
"3"
- Shift only after both token contributions are known.
The live pair now describes D(k−1),D(k). Contribution cards preserve the old values actually used. Zero counts naturally propagate impossible prefixes.
- input
"226"- phase
"commit"- history
["1","1","2","3"]- previousTwo
"2"- previousOne
"3"- length
3- oneAllowed
true- pair
26- pairAllowed
true- oneContribution
"2"- twoContribution
"1"- next
"3"
- Return the full-message tokenization count.
No standalone zero was accepted. BigInteger prevents overflow, while its growing bit length remains part of time and space costs.
- input
"226"- phase
"complete"- history
["1","1","2","3"]- previousTwo
"2"- previousOne
"3"
- Return the documented result.
Complete tables, old layers and history cards explain the algorithm but are not extra Java workspace. Arbitrary-precision values use exact decimal strings in trace data.
- result
"3"
A zero must belong to 10 or 20
Input: "11106" · Exact valid decoding count: 2
Step 1 of 11: Seed the empty-prefix identity and the actual first-digit count.
D(0)=1 allows a first token to extend an empty prefix. A leading zero makes D(1)=0. All displayed counts are exact decimal strings.
Phase: initial.
ASCII digits: "11106". Each token must be 1..26, with no leading zero.
Exact prefix counts — D(k) decodes the first k digits
- D(0)=1 — internal empty prefix
- D(1)=1
Live old predecessor pair
- previousTwo: 1
- previousOne: 1
Zero cannot stand alone. Pairs 10 and 20 are valid, while 06 and 00 are invalid. A zero prefix count means no complete tokenization reaches that boundary. Compute both old contributions before shifting; exact BigInteger values grow in bits.
All source values stay unchanged. Full grids, old layers and history cards explain state meaning; they do not add to Java reference workspace. Exact counts and products use decimal strings in trace data.
| Variable | Value |
|---|---|
| input | "11106" |
| phase | "initial" |
| history | ["1","1"] |
| previousTwo | "1" |
| previousOne | "1" |
See the affected Java block
1 import java.math.BigInteger; 2 import java.util.Objects; 3 4 public final class Solution { 5 private Solution() {} 6 private static void validate(String digits) { 7 Objects.requireNonNull(digits, "digits"); 8 if (digits.length() > 10_000) throw new IllegalArgumentException("too many digits"); 9 for (int i = 0; i < digits.length(); i++) if (digits.charAt(i) < '0' || digits.charAt(i) > '9') throw new IllegalArgumentException("ASCII digits only"); 10 } 11 public static BigInteger numDecodings(String digits) { 12 validate(digits); 13 if (digits.isEmpty()) return BigInteger.ZERO; 14 BigInteger previousTwo = BigInteger.ONE; 15 BigInteger previousOne = digits.charAt(0) == '0' ? BigInteger.ZERO : BigInteger.ONE; 16 for (int length = 2; length <= digits.length(); length++) { 17 BigInteger next = BigInteger.ZERO; 18 if (digits.charAt(length - 1) != '0') next = next.add(previousOne); 19 int pair = (digits.charAt(length - 2) - '0') * 10 + digits.charAt(length - 1) - '0'; 20 if (pair >= 10 && pair <= 26) next = next.add(previousTwo); 21 previousTwo = previousOne; 22 previousOne = next; 23 } 24 return previousOne; 25 } 26 // Baseline: enumerate valid one/two-digit pieces; short inputs only. 27 public static BigInteger baseline(String digits) { 28 validate(digits); 29 return digits.isEmpty() ? BigInteger.ZERO : decode(digits, 0); 30 } 31 private static BigInteger decode(String digits, int start) { 32 if (start == digits.length()) return BigInteger.ONE; 33 if (digits.charAt(start) == '0') return BigInteger.ZERO; 34 BigInteger count = decode(digits, start + 1); 35 if (start + 1 < digits.length()) { 36 int pair = (digits.charAt(start) - '0') * 10 + digits.charAt(start + 1) - '0'; 37 if (pair <= 26) count = count.add(decode(digits, start + 2)); 38 } 39 return count; 40 } 41 } 42
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Seed the empty-prefix identity and the actual first-digit count.
D(0)=1 allows a first token to extend an empty prefix. A leading zero makes D(1)=0. All displayed counts are exact decimal strings.
- input
"11106"- phase
"initial"- history
["1","1"]- previousTwo
"1"- previousOne
"1"
- Gate the two disjoint final-token families using old prefix counts.
A nonzero final digit may extend D(k−1). Only a pair in 10..26 may extend D(k−2); 06 is invalid even though its numeric value is six.
- input
"11106"- phase
"candidate"- history
["1","1"]- previousTwo
"1"- previousOne
"1"- length
2- oneAllowed
true- pair
11- pairAllowed
true- oneContribution
"1"- twoContribution
"1"- next
"2"
- Shift only after both token contributions are known.
The live pair now describes D(k−1),D(k). Contribution cards preserve the old values actually used. Zero counts naturally propagate impossible prefixes.
- input
"11106"- phase
"commit"- history
["1","1","2"]- previousTwo
"1"- previousOne
"2"- length
2- oneAllowed
true- pair
11- pairAllowed
true- oneContribution
"1"- twoContribution
"1"- next
"2"
- Gate the two disjoint final-token families using old prefix counts.
A nonzero final digit may extend D(k−1). Only a pair in 10..26 may extend D(k−2); 06 is invalid even though its numeric value is six.
- input
"11106"- phase
"candidate"- history
["1","1","2"]- previousTwo
"1"- previousOne
"2"- length
3- oneAllowed
true- pair
11- pairAllowed
true- oneContribution
"2"- twoContribution
"1"- next
"3"
- Shift only after both token contributions are known.
The live pair now describes D(k−1),D(k). Contribution cards preserve the old values actually used. Zero counts naturally propagate impossible prefixes.
- input
"11106"- phase
"commit"- history
["1","1","2","3"]- previousTwo
"2"- previousOne
"3"- length
3- oneAllowed
true- pair
11- pairAllowed
true- oneContribution
"2"- twoContribution
"1"- next
"3"
- Gate the two disjoint final-token families using old prefix counts.
A nonzero final digit may extend D(k−1). Only a pair in 10..26 may extend D(k−2); 06 is invalid even though its numeric value is six.
- input
"11106"- phase
"candidate"- history
["1","1","2","3"]- previousTwo
"2"- previousOne
"3"- length
4- oneAllowed
false- pair
10- pairAllowed
true- oneContribution
"0"- twoContribution
"2"- next
"2"
- Shift only after both token contributions are known.
The live pair now describes D(k−1),D(k). Contribution cards preserve the old values actually used. Zero counts naturally propagate impossible prefixes.
- input
"11106"- phase
"commit"- history
["1","1","2","3","2"]- previousTwo
"3"- previousOne
"2"- length
4- oneAllowed
false- pair
10- pairAllowed
true- oneContribution
"0"- twoContribution
"2"- next
"2"
- Gate the two disjoint final-token families using old prefix counts.
A nonzero final digit may extend D(k−1). Only a pair in 10..26 may extend D(k−2); 06 is invalid even though its numeric value is six.
- input
"11106"- phase
"candidate"- history
["1","1","2","3","2"]- previousTwo
"3"- previousOne
"2"- length
5- oneAllowed
true- pair
6- pairAllowed
false- oneContribution
"2"- twoContribution
"0"- next
"2"
- Shift only after both token contributions are known.
The live pair now describes D(k−1),D(k). Contribution cards preserve the old values actually used. Zero counts naturally propagate impossible prefixes.
- input
"11106"- phase
"commit"- history
["1","1","2","3","2","2"]- previousTwo
"2"- previousOne
"2"- length
5- oneAllowed
true- pair
6- pairAllowed
false- oneContribution
"2"- twoContribution
"0"- next
"2"
- Return the full-message tokenization count.
No standalone zero was accepted. BigInteger prevents overflow, while its growing bit length remains part of time and space costs.
- input
"11106"- phase
"complete"- history
["1","1","2","3","2","2"]- previousTwo
"2"- previousOne
"2"
- Return the documented result.
Complete tables, old layers and history cards explain the algorithm but are not extra Java workspace. Arbitrary-precision values use exact decimal strings in trace data.
- result
"2"
Leading zero has no decoding
Input: "06" · Exact valid decoding count: 0
Step 1 of 5: Seed the empty-prefix identity and the actual first-digit count.
D(0)=1 allows a first token to extend an empty prefix. A leading zero makes D(1)=0. All displayed counts are exact decimal strings.
Phase: initial.
ASCII digits: "06". Each token must be 1..26, with no leading zero.
Exact prefix counts — D(k) decodes the first k digits
- D(0)=1 — internal empty prefix
- D(1)=0
Live old predecessor pair
- previousTwo: 1
- previousOne: 0
Zero cannot stand alone. Pairs 10 and 20 are valid, while 06 and 00 are invalid. A zero prefix count means no complete tokenization reaches that boundary. Compute both old contributions before shifting; exact BigInteger values grow in bits.
All source values stay unchanged. Full grids, old layers and history cards explain state meaning; they do not add to Java reference workspace. Exact counts and products use decimal strings in trace data.
| Variable | Value |
|---|---|
| input | "06" |
| phase | "initial" |
| history | ["1","0"] |
| previousTwo | "1" |
| previousOne | "0" |
See the affected Java block
1 import java.math.BigInteger; 2 import java.util.Objects; 3 4 public final class Solution { 5 private Solution() {} 6 private static void validate(String digits) { 7 Objects.requireNonNull(digits, "digits"); 8 if (digits.length() > 10_000) throw new IllegalArgumentException("too many digits"); 9 for (int i = 0; i < digits.length(); i++) if (digits.charAt(i) < '0' || digits.charAt(i) > '9') throw new IllegalArgumentException("ASCII digits only"); 10 } 11 public static BigInteger numDecodings(String digits) { 12 validate(digits); 13 if (digits.isEmpty()) return BigInteger.ZERO; 14 BigInteger previousTwo = BigInteger.ONE; 15 BigInteger previousOne = digits.charAt(0) == '0' ? BigInteger.ZERO : BigInteger.ONE; 16 for (int length = 2; length <= digits.length(); length++) { 17 BigInteger next = BigInteger.ZERO; 18 if (digits.charAt(length - 1) != '0') next = next.add(previousOne); 19 int pair = (digits.charAt(length - 2) - '0') * 10 + digits.charAt(length - 1) - '0'; 20 if (pair >= 10 && pair <= 26) next = next.add(previousTwo); 21 previousTwo = previousOne; 22 previousOne = next; 23 } 24 return previousOne; 25 } 26 // Baseline: enumerate valid one/two-digit pieces; short inputs only. 27 public static BigInteger baseline(String digits) { 28 validate(digits); 29 return digits.isEmpty() ? BigInteger.ZERO : decode(digits, 0); 30 } 31 private static BigInteger decode(String digits, int start) { 32 if (start == digits.length()) return BigInteger.ONE; 33 if (digits.charAt(start) == '0') return BigInteger.ZERO; 34 BigInteger count = decode(digits, start + 1); 35 if (start + 1 < digits.length()) { 36 int pair = (digits.charAt(start) - '0') * 10 + digits.charAt(start + 1) - '0'; 37 if (pair <= 26) count = count.add(decode(digits, start + 2)); 38 } 39 return count; 40 } 41 } 42
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Seed the empty-prefix identity and the actual first-digit count.
D(0)=1 allows a first token to extend an empty prefix. A leading zero makes D(1)=0. All displayed counts are exact decimal strings.
- input
"06"- phase
"initial"- history
["1","0"]- previousTwo
"1"- previousOne
"0"
- Gate the two disjoint final-token families using old prefix counts.
A nonzero final digit may extend D(k−1). Only a pair in 10..26 may extend D(k−2); 06 is invalid even though its numeric value is six.
- input
"06"- phase
"candidate"- history
["1","0"]- previousTwo
"1"- previousOne
"0"- length
2- oneAllowed
true- pair
6- pairAllowed
false- oneContribution
"0"- twoContribution
"0"- next
"0"
- Shift only after both token contributions are known.
The live pair now describes D(k−1),D(k). Contribution cards preserve the old values actually used. Zero counts naturally propagate impossible prefixes.
- input
"06"- phase
"commit"- history
["1","0","0"]- previousTwo
"0"- previousOne
"0"- length
2- oneAllowed
true- pair
6- pairAllowed
false- oneContribution
"0"- twoContribution
"0"- next
"0"
- Return the full-message tokenization count.
No standalone zero was accepted. BigInteger prevents overflow, while its growing bit length remains part of time and space costs.
- input
"06"- phase
"complete"- history
["1","0","0"]- previousTwo
"0"- previousOne
"0"
- Return the documented result.
Complete tables, old layers and history cards explain the algorithm but are not extra Java workspace. Arbitrary-precision values use exact decimal strings in trace data.
- result
"0"
Public empty message convention
Input: "" · Exact valid decoding count: 0
Step 1 of 2: The public empty-message result is zero.
This API convention is separate from the internal D(0)=1 counting identity for a nonempty message.
Phase: empty.
ASCII digits: "". Each token must be 1..26, with no leading zero.
Public empty message → 0. This does not redefine the internal D(0)=1 identity used for a nonempty message.
All source values stay unchanged. Full grids, old layers and history cards explain state meaning; they do not add to Java reference workspace. Exact counts and products use decimal strings in trace data.
| Variable | Value |
|---|---|
| input | "" |
| phase | "empty" |
| history | [] |
See the affected Java block
1 import java.math.BigInteger; 2 import java.util.Objects; 3 4 public final class Solution { 5 private Solution() {} 6 private static void validate(String digits) { 7 Objects.requireNonNull(digits, "digits"); 8 if (digits.length() > 10_000) throw new IllegalArgumentException("too many digits"); 9 for (int i = 0; i < digits.length(); i++) if (digits.charAt(i) < '0' || digits.charAt(i) > '9') throw new IllegalArgumentException("ASCII digits only"); 10 } 11 public static BigInteger numDecodings(String digits) { 12 validate(digits); 13 if (digits.isEmpty()) return BigInteger.ZERO; 14 BigInteger previousTwo = BigInteger.ONE; 15 BigInteger previousOne = digits.charAt(0) == '0' ? BigInteger.ZERO : BigInteger.ONE; 16 for (int length = 2; length <= digits.length(); length++) { 17 BigInteger next = BigInteger.ZERO; 18 if (digits.charAt(length - 1) != '0') next = next.add(previousOne); 19 int pair = (digits.charAt(length - 2) - '0') * 10 + digits.charAt(length - 1) - '0'; 20 if (pair >= 10 && pair <= 26) next = next.add(previousTwo); 21 previousTwo = previousOne; 22 previousOne = next; 23 } 24 return previousOne; 25 } 26 // Baseline: enumerate valid one/two-digit pieces; short inputs only. 27 public static BigInteger baseline(String digits) { 28 validate(digits); 29 return digits.isEmpty() ? BigInteger.ZERO : decode(digits, 0); 30 } 31 private static BigInteger decode(String digits, int start) { 32 if (start == digits.length()) return BigInteger.ONE; 33 if (digits.charAt(start) == '0') return BigInteger.ZERO; 34 BigInteger count = decode(digits, start + 1); 35 if (start + 1 < digits.length()) { 36 int pair = (digits.charAt(start) - '0') * 10 + digits.charAt(start + 1) - '0'; 37 if (pair <= 26) count = count.add(decode(digits, start + 2)); 38 } 39 return count; 40 } 41 } 42
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- The public empty-message result is zero.
This API convention is separate from the internal D(0)=1 counting identity for a nonempty message.
- input
""- phase
"empty"- history
[]
- Return the documented result.
Complete tables, old layers and history cards explain the algorithm but are not extra Java workspace. Arbitrary-precision values use exact decimal strings in trace data.
- result
"0"
An impossible suffix kills all paths
Input: "100" · Exact valid decoding count: 0
Step 1 of 7: Seed the empty-prefix identity and the actual first-digit count.
D(0)=1 allows a first token to extend an empty prefix. A leading zero makes D(1)=0. All displayed counts are exact decimal strings.
Phase: initial.
ASCII digits: "100". Each token must be 1..26, with no leading zero.
Exact prefix counts — D(k) decodes the first k digits
- D(0)=1 — internal empty prefix
- D(1)=1
Live old predecessor pair
- previousTwo: 1
- previousOne: 1
Zero cannot stand alone. Pairs 10 and 20 are valid, while 06 and 00 are invalid. A zero prefix count means no complete tokenization reaches that boundary. Compute both old contributions before shifting; exact BigInteger values grow in bits.
All source values stay unchanged. Full grids, old layers and history cards explain state meaning; they do not add to Java reference workspace. Exact counts and products use decimal strings in trace data.
| Variable | Value |
|---|---|
| input | "100" |
| phase | "initial" |
| history | ["1","1"] |
| previousTwo | "1" |
| previousOne | "1" |
See the affected Java block
1 import java.math.BigInteger; 2 import java.util.Objects; 3 4 public final class Solution { 5 private Solution() {} 6 private static void validate(String digits) { 7 Objects.requireNonNull(digits, "digits"); 8 if (digits.length() > 10_000) throw new IllegalArgumentException("too many digits"); 9 for (int i = 0; i < digits.length(); i++) if (digits.charAt(i) < '0' || digits.charAt(i) > '9') throw new IllegalArgumentException("ASCII digits only"); 10 } 11 public static BigInteger numDecodings(String digits) { 12 validate(digits); 13 if (digits.isEmpty()) return BigInteger.ZERO; 14 BigInteger previousTwo = BigInteger.ONE; 15 BigInteger previousOne = digits.charAt(0) == '0' ? BigInteger.ZERO : BigInteger.ONE; 16 for (int length = 2; length <= digits.length(); length++) { 17 BigInteger next = BigInteger.ZERO; 18 if (digits.charAt(length - 1) != '0') next = next.add(previousOne); 19 int pair = (digits.charAt(length - 2) - '0') * 10 + digits.charAt(length - 1) - '0'; 20 if (pair >= 10 && pair <= 26) next = next.add(previousTwo); 21 previousTwo = previousOne; 22 previousOne = next; 23 } 24 return previousOne; 25 } 26 // Baseline: enumerate valid one/two-digit pieces; short inputs only. 27 public static BigInteger baseline(String digits) { 28 validate(digits); 29 return digits.isEmpty() ? BigInteger.ZERO : decode(digits, 0); 30 } 31 private static BigInteger decode(String digits, int start) { 32 if (start == digits.length()) return BigInteger.ONE; 33 if (digits.charAt(start) == '0') return BigInteger.ZERO; 34 BigInteger count = decode(digits, start + 1); 35 if (start + 1 < digits.length()) { 36 int pair = (digits.charAt(start) - '0') * 10 + digits.charAt(start + 1) - '0'; 37 if (pair <= 26) count = count.add(decode(digits, start + 2)); 38 } 39 return count; 40 } 41 } 42
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Seed the empty-prefix identity and the actual first-digit count.
D(0)=1 allows a first token to extend an empty prefix. A leading zero makes D(1)=0. All displayed counts are exact decimal strings.
- input
"100"- phase
"initial"- history
["1","1"]- previousTwo
"1"- previousOne
"1"
- Gate the two disjoint final-token families using old prefix counts.
A nonzero final digit may extend D(k−1). Only a pair in 10..26 may extend D(k−2); 06 is invalid even though its numeric value is six.
- input
"100"- phase
"candidate"- history
["1","1"]- previousTwo
"1"- previousOne
"1"- length
2- oneAllowed
false- pair
10- pairAllowed
true- oneContribution
"0"- twoContribution
"1"- next
"1"
- Shift only after both token contributions are known.
The live pair now describes D(k−1),D(k). Contribution cards preserve the old values actually used. Zero counts naturally propagate impossible prefixes.
- input
"100"- phase
"commit"- history
["1","1","1"]- previousTwo
"1"- previousOne
"1"- length
2- oneAllowed
false- pair
10- pairAllowed
true- oneContribution
"0"- twoContribution
"1"- next
"1"
- Gate the two disjoint final-token families using old prefix counts.
A nonzero final digit may extend D(k−1). Only a pair in 10..26 may extend D(k−2); 06 is invalid even though its numeric value is six.
- input
"100"- phase
"candidate"- history
["1","1","1"]- previousTwo
"1"- previousOne
"1"- length
3- oneAllowed
false- pair
0- pairAllowed
false- oneContribution
"0"- twoContribution
"0"- next
"0"
- Shift only after both token contributions are known.
The live pair now describes D(k−1),D(k). Contribution cards preserve the old values actually used. Zero counts naturally propagate impossible prefixes.
- input
"100"- phase
"commit"- history
["1","1","1","0"]- previousTwo
"1"- previousOne
"0"- length
3- oneAllowed
false- pair
0- pairAllowed
false- oneContribution
"0"- twoContribution
"0"- next
"0"
- Return the full-message tokenization count.
No standalone zero was accepted. BigInteger prevents overflow, while its growing bit length remains part of time and space costs.
- input
"100"- phase
"complete"- history
["1","1","1","0"]- previousTwo
"1"- previousOne
"0"
- Return the documented result.
Complete tables, old layers and history cards explain the algorithm but are not extra Java workspace. Arbitrary-precision values use exact decimal strings in trace data.
- result
"0"
Test the contract
Input:
digits="0"
Output:0No standalone zero.
Input:
digits="10"
Output:1One valid two-digit token.
Input:
digits="27"
Output:1Only 2|7 is legal.
Input:
digits="100"
Output:0The final zero has no legal predecessor token.
Input:
digits="101"
Output:110|1 survives the middle zero.
Input:
digits="١"
Output:IllegalArgumentExceptionNon-ASCII digit is rejected.
Common mistakes and counterexamples
Let 0 decode by itself
Counterexample: 06 and 30 must both return zero.
Only nonzero single digits and pairs 10..26 are legal.
Reuse the all-ones Fibonacci recurrence blindly
Counterexample: 100 has no complete tokenization even though its length is three.
Gate both predecessor contributions on actual token values.
Set the internal empty-prefix count to zero
Counterexample: 10 would lose its one valid pair token because it extends D(0).
Separate the public empty-message convention from D(0)=1.
Use int/long or shift before both contributions
Counterexample: Long all-ones inputs overflow; early shifting reuses the wrong prefix count.
Use BigInteger and a temporary next until both token checks finish.
Follow-ups
Return one decoding or all decodings.
Keep feasible predecessor choices for one witness and specify a tie policy. Enumerating every decoding requires token-path traversal and output-sensitive time, even when feasibility/counting is cached. A count alone cannot recover actual chosen letters.
Allow a wildcard character.
Derive the number of valid single-token and pair-token assignments for each wildcard pattern, multiplying predecessor counts by those multiplicities. State whether output is exact or modular and do not let a wildcard represent a standalone zero unless the contract allows it.
Process a digit stream incrementally.
Retain the last digit and two exact prefix counts; each appended digit determines the new single/pair contributions. Define empty-stream reporting separately from the internal identity. BigInteger bit growth still increases memory and arithmetic cost even though the number of state references stays constant.
Your Java attempt
Java 21 · Draft only. Your code is not compiled, executed, or graded here. Run it locally against the examples and edge cases.
Saving stores text in this browser, visible to other people using this browser profile. It does not sync to your account. Loading is always explicit.
No unsaved text changes · 134/20,000 characters
Self-review
Use the checklist to test your explanation. Checks apply to this visit.