Skip to content
Katabench
Try free

Decode Ways

Medium About 20 min Free, no account needed

How many letter strings could this digit string encode?

The brief

Letters map to numbers (A=1 ... Z=26). Given a digit string s, count the ways to decode it. A 0 decodes only as the tail of 10 or 20.

The performance bar

The obvious approach recurses on one- and two-digit takes, 2^n on a string of 80 ones (the hidden test), whose answer is a 17-digit Fibonacci number. You need to avoid recomputing the same suffix over and over, O(n).

Starter code

C#
using System;

public class Solution
{
    // TODO: return the number of decodings of the digit string.
    public long NumDecodings(string s)
    {
        throw new NotImplementedException();
    }
}

How it is graded

Visible examples help you iterate. Hidden tests then cover edge cases and larger inputs, and every test reports server-measured time and allocated bytes.

C# coding challenges →

What it practices

Dynamic programming
Define subproblems and a recurrence, then reuse solved subproblems instead of recomputing them.

Do these first

Related katas