20 · String Parsing & Expression Evaluation

#13 Roman to Integer

frequently reported atBloomberg Microsoft Google TCS Amazon Meta

the problem

In plain words

Roman numerals use seven letters, here from biggest to smallest: M = 1000, D = 500, C = 100, L = 50, X = 10, V = 5 and I = 1. Usually the letters go from big to small and their values add up (VIII = 8). In six cases a smaller letter sits just before a bigger one and is subtracted instead: IV = 4, IX = 9, XL = 40, XC = 90, CD = 400, CM = 900. Given a valid numeral s, return its value.

in s = "III"

out 3

in s = "LVIII"

out 58

50 + 5 + 3.

in s = "MCMXCIV"

out 1994

M + CM + XC + IV = 1000 + 900 + 90 + 4.

1 ≤ s.length ≤ 15
s uses only I, V, X, L, C, D, M
s is a valid numeral for a value from 1 to 3999

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternString parsing

where this runsExcel's ARABIC() function does this conversion (and is more forgiving: it also accepts non-standard numerals like MXMVII).

A symbol is subtracted exactly when the next symbol is bigger. Peek one ahead, then add or subtract — one pass.

solutions

From brute force to optimal

Spell each subtractive pair the long, additive way (CM → DCCCC, IV → IIII). Then every symbol simply adds.

Replace CM, CD, XC, XL, IX, IV with their additive spellings.
Add up the value of every symbol.

timeO(n)

Six replace passes over at most 15 characters, then one sum.

spaceO(n)

Each replace builds a new String.

java

1class Solution {2    public int romanToInt(String s) {3        // Spell each subtractive pair out the long, additive way. Longer pairs first.4        s = s.replace("CM", "DCCCC").replace("CD", "CCCC")5             .replace("XC", "LXXXX").replace("XL", "XXXX")6             .replace("IX", "VIIII").replace("IV", "IIII");7        int total = 0;8        for (char c : s.toCharArray()) total += value(c); // now every symbol simply adds9        return total;10    }11 12    private int value(char c) {13        return switch (c) {14            case 'I' -> 1;15            case 'V' -> 5;16            case 'X' -> 10;17            case 'L' -> 50;18            case 'C' -> 100;19            case 'D' -> 500;20            default -> 1000; // 'M'21        };22    }23}

Walk left to right. If the next symbol is bigger, subtract this one; otherwise add it.

total = 0.
For each i: v = value(s[i]).
If i + 1 < n and v < value(s[i + 1]): total −= v. Else total += v.
Return total.

timeO(n)

One look at each symbol and its neighbour.

spaceO(1)

A counter and a switch for the values.

java

1class Solution {2    public int romanToInt(String s) {3        int total = 0;4        for (int i = 0; i < s.length(); i++) {5            int v = value(s.charAt(i));6            if (i + 1 < s.length() && v < value(s.charAt(i + 1))) {7                total -= v; // smaller before bigger: the I in IV counts as -18            } else {9                total += v;10            }11        }12        return total;13    }14 15    private int value(char c) {16        return switch (c) {17            case 'I' -> 1;18            case 'V' -> 5;19            case 'X' -> 10;20            case 'L' -> 50;21            case 'C' -> 100;22            case 'D' -> 500;23            default -> 1000; // 'M'24        };25    }26}

sim

Dry run

loading simulation…

java

1class Solution {2    public int romanToInt(String s) {3        int total = 0;4        for (int i = 0; i < s.length(); i++) {5            int v = value(s.charAt(i));6            if (i + 1 < s.length() && v < value(s.charAt(i + 1))) {7                total -= v; // smaller before bigger: the I in IV counts as -18            } else {9                total += v;10            }11        }12        return total;13    }14 15    private int value(char c) {16        return switch (c) {17            case 'I' -> 1;18            case 'V' -> 5;19            case 'X' -> 10;20            case 'L' -> 50;21            case 'C' -> 100;22            case 'D' -> 500;23            default -> 1000; // 'M'24        };25    }26}

in the room

How to say it in the interview

talk track

Confirm the input is always a valid numeral, so I don't need to reject "IIV".
State the rule: subtract a symbol when the next one is bigger, otherwise add it.
Walk MCMXCIV aloud: +1000 −100 +1000 −10 +100 −1 +5 = 1994.
Mention the value lookup: a switch or an int[128] table is cheaper than a HashMap<Character, Integer>.

traps

Comparing with the previous symbol, then forgetting to undo what you already added: IV becomes 1 + 5 = 6.
Peeking past the end: check i + 1 < n before reading s.charAt(i + 1).

what they ask next

Follow-ups

Also reject invalid numerals like IIII, VX or IC?

Convert, then convert the value back with the greedy table (Integer to Roman) and compare the strings. They match exactly for standard numerals. O(1) in this range.

Why not a HashMap<Character, Integer> for the values?

It works, but it boxes and hashes on every character. A switch, or int[] v = new int[128]; v['I'] = 1; …, does the same in a plain array lookup.

before you submit

Edge cases to test

One symbol: "I" → 1.
Pairs side by side: "CDXLIV" → 444.
The largest value "MMMCMXCIX" → 3999; the longest numeral "MMMDCCCLXXXVIII" → 3888 (15 symbols).

practise next