Back to Strings
Q18Question 18 of 61

Decode Ways — count decodings of a digit string

Key Concepts
  • String manipulation: reverse, palindrome, anagram check
  • Character frequency counting with HashMap
  • Substring search, pattern matching
  • String is immutable in Java — use StringBuilder for modification
  • Create dp of size n+1 with dp[0]=1 (one way to decode the empty string) and dp[1] equal to one if the first digit is not zero, otherwise zero.
  • For each position i from 2 to n, add dp[i−1] when the current single digit is between 1 and 9, and add dp[i−2] when the two-digit number formed with the previous digit is between 10 and 26.
  • charAt(i-1) != '0') dp[i] += dp[i-1]; int two = Integer.

Definition

dp[i] = (single valid ? dp[i−1] : 0) + (pair valid ? dp[i−2] : 0).

1D DP like Fibonacci with validity guards, where dp[i] is the number of decodings of the first i digits. dp[i] adds dp[i−1] if the single digit is 1 through 9, and adds dp[i−2] if the two-digit number is 10 through 26. Base dp[0]=1. Time O(n), space O(1) with rolling variables.

A back-office clerk at National Bank of India decodes a numeric reference where each letter was stored as a number. At each position she can read one digit as a letter if it is not zero, or combine it with the previous digit if together they form ten to twenty-six, summing both ways.

Understanding the Concepts

What is the problem?

Decode Ways — count decodings of a digit string. A message of digits is encoded where 1 maps to A through 26 maps to Z. Given a digit string, count how many ways it can be decoded.

How does the approach work?

Create dp of size n+1 with dp[0]=1 (one way to decode the empty string) and dp[1] equal to one if the first digit is not zero, otherwise zero. For each position i from 2 to n, add dp[i−1] when the current single digit is between 1 and 9, and add dp[i−2] when the two-digit number formed with the previous digit is between 10 and 26. For example: if (s.charAt(i-1) != '0') dp[i] += dp[i-1]; int two = Integer.parseInt(s.substring(i-2, i)); if (two >= 10 && two <= 26) dp[i] += dp[i-2];.

The two validity guards are everything. A leading zero cannot stand alone, and a pair above 26 or below 10 (like 09) is invalid. The answer is dp[n].

The time is O(n) and space is O(1) if you keep only the last two values. A senior nuance is that strings containing a zero that cannot pair (like 30) decode to zero ways, so careful zero handling is the main source of bugs.

What is the banking use case?

Problem 1 — At National Bank of India, archived references stored letters as numbers, and a clerk must count how many distinct letter strings a numeric reference could represent to flag ambiguous ones for manual review. This is exactly how Decode Ways works.
Problem 2 — Zeros and pairs above twenty-six make some readings invalid, so naive counting is wrong. This is exactly why the two validity guards gate each addition.

The mini-project builds a ReferenceDecoder, a BankLogFormatter, and a runnable demo.

How do you implement this in Java?

JAVA
// ─── File: src/main/java/com/bank/ref/ReferenceDecoder.java ───
package com.bank.ref;

import java.util.logging.Logger;

public class ReferenceDecoder {

    private static final Logger log = Logger.getLogger(ReferenceDecoder.class.getName());

    public int numDecodings(String s) {
        int n = s.length();
        if (n == 0 || s.charAt(0) == '0') return 0;
        int[] dp = new int[n + 1];
        dp[0] = 1;                                     // empty string: one way
        dp[1] = 1;                                     // first digit is non-zero here
        for (int i = 2; i <= n; i++) {
            if (s.charAt(i - 1) != '0') {              // single digit 1..9 valid
                dp[i] += dp[i - 1];
            }
            int two = Integer.parseInt(s.substring(i - 2, i));
            if (two >= 10 && two <= 26) {              // two-digit 10..26 valid
                dp[i] += dp[i - 2];
            }
        }
        int result = dp[n];
        log.info(() -> "numDecodings(" + s + ") = " + result);
        return result;
    }
}
JAVA
// ─── File: src/main/java/com/bank/ref/BankLogFormatter.java ───
package com.bank.ref;

import java.util.logging.Formatter;
import java.util.logging.LogRecord;
import java.time.Instant;

public class BankLogFormatter extends Formatter {
    @Override
    public String format(LogRecord record) {
        return String.format("%s [%s] %s%n",
                Instant.ofEpochMilli(record.getMillis()),
                record.getLevel(),
                record.getMessage());
    }
}
JAVA
// ─── File: src/main/java/com/bank/ref/DecodeWaysDemo.java ───
package com.bank.ref;

import java.util.logging.ConsoleHandler;
import java.util.logging.Logger;

public class DecodeWaysDemo {

    private static final Logger log = Logger.getLogger(DecodeWaysDemo.class.getName());

    static {
        Logger root = Logger.getLogger("");
        for (var h : root.getHandlers()) root.removeHandler(h);
        ConsoleHandler handler = new ConsoleHandler();
        handler.setFormatter(new BankLogFormatter());
        root.addHandler(handler);
    }

    public static void main(String[] args) {
        log.info("National Bank of India — Reference Decoder (Decode Ways)");
        ReferenceDecoder decoder = new ReferenceDecoder();
        log.info("'226' → " + decoder.numDecodings("226")); // 3 (BZ, VF, BBF)
        log.info("'06' → " + decoder.numDecodings("06"));    // 0 (leading zero)
    }
}

What is the project structure?

DIAGRAM
reference-decode-service/
├── pom.xml
├── src/main/java/com/bank/ref/
│   ├── DecodeWaysDemo.java          (main runnable demo)
│   ├── ReferenceDecoder.java        (1D decode-ways DP)
│   └── BankLogFormatter.java
└── src/test/java/com/bank/ref/
    └── ReferenceDecoderTest.java

How do you build and run?

BASH
# Compile
javac -d target/classes src/main/java/com/bank/ref/*.java

# Run
java -cp target/classes com.bank.ref.DecodeWaysDemo

What is the step-by-step walkthrough?

The input string is 226.

Step 1: dp of zero is one and dp of one is one because the first digit two is not zero.
Step 2: At position two the single digit two is valid adding dp of one, and the pair twenty-two is between ten and twenty-six adding dp of zero, giving dp of two equal to two.
Step 3: At position three the single digit six is valid adding dp of two, and the pair twenty-six is valid adding dp of one, giving dp of three equal to three.
Step 4: The answer is dp of three which is three, matching BZ, VF, and BBF.
Step 5: For 06 the leading zero makes the first digit invalid, so the method returns zero immediately.
DIAGRAM
2026-10-27T02:30:00Z [INFO] National Bank of India — Reference Decoder (Decode Ways)
2026-10-27T02:30:00Z [INFO] numDecodings(226) = 3
2026-10-27T02:30:00Z [INFO] '226' → 3
2026-10-27T02:30:00Z [INFO] numDecodings(06) = 0
2026-10-27T02:30:00Z [INFO] '06' → 0

What is the high-level design?

DIAGRAM
  ═══ HLD — Reference Decoder ═══

  ┌────────────┐ digits ┌──────────────┐ ┌──────────────────┐
  │ Archive UI │───────→│ Decoder Svc  │→│ rolling dp[i-1,2]│
  └────────────┘        │ (Spring ×N)  │ └──────────────────┘
                        └──────┬───────┘
                               │ #decodings → ambiguity flag
                               ▼
                         Manual Review Queue

What is the low-level design?

DIAGRAM
  ═══ LLD — Decode Ways ═══

  ┌─ Technique ──────────────────────────────────────────────┐
  │  dp[i]+=dp[i-1] if 1..9 ; dp[i]+=dp[i-2] if 10..26        │
  │  Fibonacci-shaped; zeros/pairs>26 are the bug sources     │
  └──────────────────────────────────────────────────────────┘

  ┌───────────────────────────────────────┐
  │   ReferenceDecoder                    │
  │  + numDecodings(s): int               │ O(n), O(1) space
  └───────────────────────────────────────┘

What is the time and space complexity?

Analyze the solution based on the algorithm used. Consider both the time to process input and the space required for any data structures.

What are common mistakes?

Common mistakes include off-by-one errors, not handling edge cases like empty input, and not considering the constraints of the problem.

What are the edge cases?

Edge cases include empty input, single element input, all identical elements, and boundary values.

What should a senior engineer know?

A senior engineer should understand the time-space tradeoffs, be able to explain the algorithm clearly, and know when this technique applies versus alternatives.

Visual Overview

DIAGRAM
  s = 2 2 6
  dp[0]=1 , dp[1]=1
  dp[2]: single '2'→+dp[1]=1 ; pair "22"(10..26)→+dp[0]=1 ⇒ 2
  dp[3]: single '6'→+dp[2]=2 ; pair "26"(10..26)→+dp[1]=1 ⇒ 3
  answer = dp[3] = 3

Key Takeaway

Decode Ways is a one-dimensional dynamic programming problem shaped like Fibonacci but with validity guards. I define dp of i as the number of ways to decode the first i digits. The base cases are dp of zero equal to one for the empty string and dp of one equal to one when the first digit is not zero.

For each later position I make two guarded additions. If the current single digit is between one and nine it can stand alone as a letter, so I add dp of the previous position. If the two-digit number formed with the digit before it is between ten and twenty-six it forms a valid letter, so I add dp of the position two back. The two guards are the whole problem, because a leading zero cannot stand alone and a pair like oh-nine or thirty is invalid.

In my project at National Bank of India, archived references stored letters as numbers, and a clerk had to count how many distinct letter strings a numeric reference could represent so ambiguous ones went to manual review. I used this linear DP with constant space by keeping only the last two counts, and I was careful with zeros because mishandling them is the classic source of wrong answers.

Remember one sentence: understand the core algorithm and apply it to banking domain problems.

---

Share
Use ← → arrow keys to navigate