Roman to Integer

import sys

class Solution:
    # O(N) Time, O(1) Space - Right-to-Left Traversal (Cleanest Optimal)
    def romanToInt_optimal(self, s: str) -> int:
        roman_map = {'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000}
        total = 0
        
        # Start with the value of the last character
        total += roman_map[s[-1]]
        
        # Iterate from the second-to-last character backward
        for i in range(len(s) - 2, -1, -1):
            current_val = roman_map[s[i]]
            prev_val = roman_map[s[i+1]]
            
            if current_val < prev_val:
                total -= current_val
            else:
                total += current_val
                
        return total

    # Brute Force: O(N) Time, O(1) Space - Left-to-Right Check
    def romanToInt_brute(self, s: str) -> int:
        roman_map = {'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000}
        total = 0
        N = len(s)
        
        for i in range(N):
            current_val = roman_map[s[i]]
            
            if i < N - 1:
                next_val = roman_map[s[i+1]]
                
                # Check for the subtraction case (IV, IX, XL, etc.)
                if current_val < next_val:
                    total -= current_val
                    continue # Skip addition, subtract and move to next char
            
            # Default case: add the value
            total += current_val
            
        return total
    
    def solve(self):
        try:
            s = sys.stdin.readline().strip()
        except:
            return
        
        result = self.romanToInt_optimal(s)
        print(result)

if __name__ == "__main__":
    Solution().solve()

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

class Solution {
    
    private final Map<Character, Integer> romanMap = new HashMap<>() {{
        put('I', 1);
        put('V', 5);
        put('X', 10);
        put('L', 50);
        put('C', 100);
        put('D', 500);
        put('M', 1000);
    }};

    // Optimized: O(N) Time, O(1) Space - Right-to-Left Traversal (Cleaner Logic)
    public int romanToInt_optimal(String s) {
        if (s == null || s.isEmpty()) return 0;
        
        int total = romanMap.get(s.charAt(s.length() - 1)); // Start with the last character
        
        // Iterate from the second-to-last character backward
        for (int i = s.length() - 2; i >= 0; i--) {
            int currentVal = romanMap.get(s.charAt(i));
            int nextVal = romanMap.get(s.charAt(i+1));
            
            if (currentVal < nextVal) {
                total -= currentVal; // Subtraction case
            } else {
                total += currentVal; // Addition case
            }
        }
        return total;
    }

    // Brute Force: O(N) Time, O(1) Space - Left-to-Right Check (More complex index management)
    public int romanToInt_brute(String s) {
        int total = 0;
        int N = s.length();

        for (int i = 0; i < N; ++i) {
            int currentVal = romanMap.get(s.charAt(i));
            
            if (i < N - 1) {
                int nextVal = romanMap.get(s.charAt(i+1));
                
                // Check for subtraction case and handle the pair
                if (currentVal < nextVal) {
                    total += (nextVal - currentVal);
                    i++; // Crucial: Skip the next character
                    continue;
                }
            }
            // Default case: add the current character's value
            total += currentVal;
        }
        return total;
    }
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        if (!scanner.hasNextLine()) return;
        String s = scanner.nextLine();
        
        Solution solution = new Solution();
        int result = solution.romanToInt_optimal(s);
        System.out.println(result);
        scanner.close();
    }
}

#include <iostream>
#include <string>
#include <unordered_map>

using namespace std;

class Solution {
private:
    unordered_map<char, int> roman_map = {
        {'I', 1}, {'V', 5}, {'X', 10}, {'L', 50}, 
        {'C', 100}, {'D', 500}, {'M', 1000}
    };

public:
    // Optimized: O(N) Time, O(1) Space - Right-to-Left Traversal
    int romanToInt_optimal(string s) {
        if (s.empty()) return 0;
        
        int total = roman_map[s.back()]; // Start with the last character
        
        // Iterate from the second-to-last character backward
        for (int i = s.length() - 2; i >= 0; --i) {
            int current_val = roman_map[s[i]];
            int next_val = roman_map[s[i+1]];
            
            // Subtraction case (IV, IX, etc.)
            if (current_val < next_val) {
                total -= current_val;
            } else {
                total += current_val;
            }
        }
        return total;
    }

    // Brute Force: O(N) Time, O(1) Space - Left-to-Right Check (Requires careful skip logic)
    int romanToInt_brute(string s) {
        int total = 0;
        int N = s.length();

        for (int i = 0; i < N; ++i) {
            int current_val = roman_map[s[i]];
            
            if (i < N - 1) {
                int next_val = roman_map[s[i+1]];
                
                // If subtraction case, add the pair's difference and skip the next character
                if (current_val < next_val) {
                    total += (next_val - current_val);
                    i++; // Skip the next character as it was just accounted for
                    continue;
                }
            }
            // Default case: add the current character's value
            total += current_val;
        }
        return total;
    }

    void solve() {
        string s;
        if (!getline(cin, s)) return;
        
        int result = romanToInt_optimal(s);
        cout << result << endl;
    }
};

int main() {
    Solution().solve();
    return 0;
}