Roman to Integer

Problem

Roman numerals are represented by seven symbols: I, V, X, L, C, D, M with values 1, 5, 10, 50, 100, 500, 1000.

Numerals are usually written largest→smallest left to right, but six subtractive cases apply:

• IV = 4, IX = 9
• XL = 40, XC = 90
• CD = 400, CM = 900

Given a Roman numeral string, convert it to an integer.

Input / Output Format

Input: String s. Output: Integer value.

Examples

Example 1

Input: s = "III" → Output: 3

Example 2

Input: s = "LVIII" → Output: 58 (L=50, V=5, III=3)

Example 3

Input: s = "MCMXCIV" → Output: 1994 (M=1000, CM=900, XC=90, IV=4)

Approach Hints

• Right-to-Left scan — Start from the right, accumulate values. If current value < running max, subtract; else add.
• Left-to-Right scan — Compare s[i] to s[i+1]. If smaller, subtract; else add.
• Build a map {I:1, V:5, X:10, L:50, C:100, D:500, M:1000}.
• Time: O(n). Space: O(1).