String Symbol Mapping

Description

Converting between a number and its written form, such as Roman numerals, spreadsheet column letters or "2h 5m", is a table plus a loop. The table is the easy part. Subtractive pairs, a numbering system with no zero digit, and input that isn't in its standard form are where these conversions go wrong. This skill covers greedy encoding, lookahead decoding, base 26 with no zero, and how to validate what you decode.

We'll go from simple to more technical:

1. The pattern: greedy encoding from a value table, and decoding with one symbol of lookahead.
2. A second flavor: spreadsheet columns, base 26 with no zero.
3. Where symbol mappings show up (spreadsheets, versions, durations, IDs).
4. What breaks it: missing pairs, the last symbol, no zero digit, untrusted input.

The approach

int romanToInt(String s) {
    Map<Character, Integer> value = Map.of('I', 1, 'V', 5, 'X', 10, 'L', 50, 'C', 100, 'D', 500, 'M', 1000);
    int total = 0;
    for (int i = 0; i < s.length(); i++) {
        int cur = value.get(s.charAt(i));
        if (i + 1 < s.length() && cur < value.get(s.charAt(i + 1))) total -= cur;   // the I in IV
        else total += cur;
    }
    return total;
}

String intToRoman(int num) {
    int[] values =     {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
    String[] symbols = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < values.length; i++) {
        while (num >= values[i]) { num -= values[i]; sb.append(symbols[i]); }   // greedy: largest first
    }
    return sb.toString();
}

def roman_to_int(s: str) -> int:
    value = {"I": 1, "V": 5, "X": 10, "L": 50, "C": 100, "D": 500, "M": 1000}
    total = 0
    for i, ch in enumerate(s):
        cur = value[ch]
        if i + 1 < len(s) and cur < value[s[i + 1]]:
            total -= cur                             # the I in IV
        else:
            total += cur
    return total


def int_to_roman(num: int) -> str:
    table = [(1000, "M"), (900, "CM"), (500, "D"), (400, "CD"), (100, "C"), (90, "XC"),
             (50, "L"), (40, "XL"), (10, "X"), (9, "IX"), (5, "V"), (4, "IV"), (1, "I")]
    parts = []
    for value, symbol in table:
        while num >= value:                          # greedy: largest first
            num -= value
            parts.append(symbol)
    return "".join(parts)

Decoding needs one look ahead: a symbol smaller than the next one is subtracted, and the last symbol has no next one (hence the bounds check). Encoding is greedy - take the largest value that fits, repeatedly - and putting the six subtractive pairs in the table as their own entries is what keeps it a plain loop. Leave out CD, XL and IV and 444 comes out as CCCCXXXXIIII. Greedy is correct here because the table is canonical, like coins 1, 5, 10, 25; with coins 1, 3 and 4, greedy pays 6 as 4 + 1 + 1 instead of 3 + 3.

A second flavor: a positional system with no zero

Spreadsheet columns run A..Z, then AA, AB, ...: base 26 with digits 1 to 26 and no zero ("bijective" base 26). Reading one is ordinary positional decoding (Horner's rule); writing one needs a shift:

int titleToNumber(String t) {                   // "AB" -> 1 * 26 + 2 = 28
    int v = 0;
    for (char c : t.toCharArray()) v = v * 26 + (c - 'A' + 1);
    return v;
}

String convertToTitle(int n) {                  // 28 -> "AB"
    StringBuilder sb = new StringBuilder();
    while (n > 0) {
        n--;                                    // map 1..26 to 0..25 before taking the digit
        sb.append((char) ('A' + n % 26));
        n /= 26;
    }
    return sb.reverse().toString();
}

def title_to_number(t: str) -> int:                  # "AB" -> 1 * 26 + 2 = 28
    v = 0
    for ch in t:
        v = v * 26 + (ord(ch) - ord("A") + 1)
    return v


def convert_to_title(n: int) -> str:                 # 28 -> "AB"
    letters = []
    while n > 0:
        n, r = divmod(n - 1, 26)                     # map 1..26 to 0..25 before taking the digit
        letters.append(chr(ord("A") + r))
    return "".join(reversed(letters))

Without the n--, 26 has remainder 0, which has no letter; decrementing only inside the letter calculation ((n - 1) % 26) but dividing the original n turns 26 into "AZ". The largest Excel column, XFD, is 24 * 676 + 6 * 26 + 4 = 16,384.

Where you'll see it

Formatting sizes and durations ("1.5 GB", "2h 5m") greedily takes the largest unit that fits; spreadsheet and report column labels use bijective base 26; short-URL and ID schemes encode numbers in base 62 (which does have a zero digit). Any closed set of codes (status codes to labels, country codes to names) is the same table lookup.

Which tool for which job?

Common mistakes

Check yourself

Try to answer before opening each one - recalling beats re-reading.

1. In MCMLXXIV, how does the decoder know to subtract the first C?

2. Why does the encoding table include CM, CD, XC, XL, IX and IV?

3. Why does the column-title encoder decrement n before n % 26?

Key takeaways

• Decode with one look ahead: subtract a symbol smaller than its right neighbor, and bounds-check the last one.
• Encode greedily, largest first, with the subtractive pairs as table entries.
• Greedy is only correct for canonical tables (1, 5, 10, 25 yes; 1, 3, 4 no).
• Spreadsheet columns are base 26 with no zero: n-- before % 26 and / 26.
• Decoders accept invalid input; validate by round-tripping.