69. Roman Numeral to Integer

Given a valid Roman numeral string (using symbols I, V, X, L, C, D, M), convert it to its integer value.

Input: The input is a single line containing a valid Roman numeral string. Output: Print a single integer - the numeral's integer value.

1 <= value <= 3999

The subtractive rule only ever applies to a SMALLER value immediately followed by a LARGER one - checking exactly this local relationship (current vs. next) is sufficient; no lookahead beyond one symbol is ever needed.

Convert a Roman numeral (like 'XIV') into its normal integer value. Brute force: Try to match whole known Roman 'chunks' (like 'IV', 'IX', 'XL') against the string directly with string replacement tricks - this works but is fragile and harder to reason about correctness for compared to the direct left-to-right scan-and-compare-next approach. Optimised: Comparing each symbol's value only to the symbol IMMEDIATELY after it (deciding add-or-subtract on the fly) correctly captures every subtractive case (IV, IX, XL, XC, CD, CM) without needing a special lookup table of two-character combinations - a single linear scan handles everything uniformly.

Map each Roman symbol to its integer value in a lookup table (I=1, V=5, X=10, L=50, C=100, D=500, M=1000), then scan the string once comparing each symbol's value to the value of the symbol right after it: if the current value is smaller than the next one, subtract it from the running total (this captures the subtractive cases like IV or IX generically); otherwise, add it. This generalizes the six-case brute-force logic into a single rule driven by a value comparison, using a small constant-size map instead of hardcoded string matching. Time: O(n) Space: O(1)

Use the same value map, but scan the string from right to left while tracking the largest value seen so far. For each symbol (moving right to left), if its value is at least the largest value seen so far, add it to the total and update the largest-seen value; otherwise (it's smaller than something to its right, meaning it's a subtractive prefix like the I in IV), subtract it instead. This needs no lookahead at all - each character's contribution is decided using only information already accumulated - making it the simplest, single-direction, branch-minimal pass over the string. Time: O(n) Space: O(1)

Scan the string from left to right and use an explicit chain of checks for each of the six special two-character subtractive combinations (IV, IX, XL, XC, CD, CM): if the current two characters match one of these, add its special value and advance two positions; otherwise look up the single character's standard value, add it, and advance one position. This works, since it's just a direct hard-coded encoding of the Roman numeral rules, but the special-casing makes it rigid and harder to extend or reuse for other symbol sets. Time: O(n) Space: O(1)

1. Map each Roman symbol to its value (I=1, V=5, X=10, L=50, C=100, D=500, M=1000). 2. Scan the string left to right, adding each symbol's value to a running total. 3. EXCEPT: if a symbol's value is smaller than the value of the symbol right after it, SUBTRACT it instead of adding (this handles special cases like IV=4, IX=9, XL=40).

Time: O(n) - one single pass through the Roman numeral string. Space: O(1) - just a fixed lookup table of 7 symbol values and a running total.

Subtractive-notation pairs like IV, IX, XL, XC, CD, CM; the maximum representable value 3999 (MMMCMXCIX); the minimum value 1 (I).

Be ready to also discuss the REVERSE problem (integer to Roman) as a natural, commonly-asked follow-up - it uses a similar greedy, largest-value-first idea.