☕ DSA Java Articles

Topics › Strings › Medium String Problems

Roman to Integer

Medium TUF ID 903 A2ZSDE

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

Roman numerals use seven symbols: I = 1, V = 5, X = 10, L = 50, C = 100, D = 500, M = 1000. A numeral is normally written with its symbols in non-increasing order and its value is the sum of the symbols: XXVII is 10 + 10 + 5 + 1 + 1 = 27. There are exactly six exceptions, the subtractive pairs, where a smaller symbol placed immediately before a larger one is subtracted instead of added: IV = 4, IX = 9, XL = 40, XC = 90, CD = 400, CM = 900.

Given a string s that is a valid Roman numeral, return the integer it represents.

Constraints: 1 ≤ |s| ≤ 15; s contains only the seven symbols above and is guaranteed to be a valid numeral in the range 1 to 3999.

Example 1

s = "LVIII"
answer = 58            // L = 50, V = 5, III = 3

Example 2

s = "MCMXCIV"
answer = 1994          // M = 1000, CM = 900, XC = 90, IV = 4

Example 3

s = "III"
answer = 3             // three symbols, all added

Approach 1: Brute force, a table of all thirteen tokens

Intuition. Treat the numeral as a sequence of tokens drawn from a fixed vocabulary of thirteen: the seven single symbols plus the six subtractive pairs. Reading left to right, at every position we must decide whether the next token is one letter or two. The rule is simple: if the next two characters form one of the six pairs, they belong together, because in a valid numeral a smaller symbol is never followed by a larger one except inside a subtractive pair. So “try the two-letter token first, fall back to one letter” is a correct greedy tokeniser.

Algorithm.

  1. Build a map from each of the 13 tokens to its value.
  2. Set total = 0 and i = 0.
  3. While i < n: if i + 1 < n and s[i..i+1] is in the map, add its value and advance by 2; otherwise add the value of s[i] and advance by 1.
  4. Return total.
static int bruteForce(String s) {
    Map<String, Integer> table = new HashMap<>();
    table.put("I", 1);    table.put("IV", 4);    table.put("V", 5);    table.put("IX", 9);
    table.put("X", 10);   table.put("XL", 40);   table.put("L", 50);   table.put("XC", 90);
    table.put("C", 100);  table.put("CD", 400);  table.put("D", 500);  table.put("CM", 900);
    table.put("M", 1000);
    int total = 0, i = 0, n = s.length();
    while (i < n) {
        if (i + 1 < n && table.containsKey(s.substring(i, i + 2))) {
            total += table.get(s.substring(i, i + 2));
            i += 2;
        } else {
            total += table.get(s.substring(i, i + 1));
            i += 1;
        }
    }
    return total;
}

Complexity. Time O(n): each character is consumed once, and the map has constant size. Space O(1): thirteen entries regardless of the input. The approach does allocate a short substring per step, which is its only practical cost. It is also the most literal transcription of the rules, which makes it a good first answer in an interview before refining.

The thirteen-entry table encodes the subtraction rule by enumeration. The next approach encodes it by a single comparison, which removes the table and the substrings.

Approach 2: Optimal, compare each symbol with its right neighbour

Intuition. Look at what a subtractive pair really does. In CM, the M is added as usual and the C is subtracted: -100 + 1000 = 900. So the only symbols that are ever subtracted are those that are immediately followed by a strictly larger symbol. Everything else is added. That turns the whole problem into one pass with one comparison per character: subtract value(s[i]) if value(s[i]) < value(s[i+1]), otherwise add it.

Why is this exact? A valid numeral is a sequence of tokens as in Approach 1. Inside a subtractive pair the first symbol is smaller than the second, so the rule subtracts it, and the second symbol is either the last character or followed by something no larger (tokens appear in non-increasing order of value), so it is added. A single-symbol token is never followed by a larger symbol, otherwise the two would have formed a subtractive pair. Hence the rule assigns every character the sign it has in the token decomposition.

The helper converts one symbol to its value with a switch expression and rejects anything that is not a Roman symbol:

static int value(char c) {
    return switch (c) {
        case 'I' -> 1;
        case 'V' -> 5;
        case 'X' -> 10;
        case 'L' -> 50;
        case 'C' -> 100;
        case 'D' -> 500;
        case 'M' -> 1000;
        default -> throw new IllegalArgumentException("not a Roman symbol: " + c);
    };
}

Algorithm.

  1. Set total = 0.
  2. For each index i: let cur = value(s[i]).
    • If i + 1 < n and cur < value(s[i+1]), do total -= cur.
    • Otherwise do total += cur.
  3. Return total.
static int optimal(String s) {
    int total = 0, n = s.length();
    for (int i = 0; i < n; i++) {
        int cur = value(s.charAt(i));
        if (i + 1 < n && cur < value(s.charAt(i + 1))) total -= cur;
        else total += cur;
    }
    return total;
}

Dry run on s = "MCMXCIV":

i s[i] cur next action total
0 M 1000 100 add 1000
1 C 100 1000 subtract 900
2 M 1000 10 add 1900
3 X 10 100 subtract 1890
4 C 100 1 add 1990
5 I 1 5 subtract 1989
6 V 5 none add 1994

Complexity. Time O(n): one comparison and one addition per character. Space O(1): no table, no substrings.

Approach 3: Optimal, scan from the right

Intuition. The same rule can be applied while walking from the end of the string towards the front. The symbol processed in the previous step is the right neighbour of the current one, so remembering a single value prev replaces the look-ahead s[i+1] and removes the bounds check. The very last symbol is always added, which is what happens naturally when prev starts at 0: nothing is smaller than 0.

Algorithm.

  1. Set total = 0 and prev = 0.
  2. For i from n - 1 down to 0: let cur = value(s[i]). If cur < prev subtract it, otherwise add it. Then set prev = cur.
  3. Return total.
static int optimalRightToLeft(String s) {
    int total = 0, prev = 0;
    for (int i = s.length() - 1; i >= 0; i--) {
        int cur = value(s.charAt(i));
        if (cur < prev) total -= cur;
        else total += cur;
        prev = cur;
    }
    return total;
}

Complexity. Time O(n), space O(1), identical to Approach 2. The two are interchangeable; the right-to-left form is slightly tidier because the loop body has no index arithmetic.

Note that the comparison is strict in both directions of scanning. Equal neighbours, as in III or XX, must be added, and cur < prev is false for equal values.

Edge cases and pitfalls