Excel Sheet Column Title

NeetCode: Excel Sheet Column Title · LeetCode: 168. Excel Sheet Column Title · Difficulty: Easy

Given a positive integer columnNumber, return its title as it appears in a spreadsheet: 1 -> "A", 2 -> "B", ..., 26 -> "Z", 27 -> "AA", 28 -> "AB", ...

Example

Text

Input:  columnNumber = 1      Output: "A"
Input:  columnNumber = 28     Output: "AB"
Input:  columnNumber = 701    Output: "ZY"

Brute force: count up title by title

Start at "A" and apply the spreadsheet's own "next title" rule columnNumber - 1 times: increment the last letter, and when a Z wraps to A carry into the letter on its left, adding a new leading A if the carry falls off the front. The work is proportional to the number itself, even though the answer has only a few letters.

A String is immutable, so the title lives in a StringBuilder, which allows setCharAt and insert. In Java, char arithmetic produces an int, so incrementing a letter needs a cast back to char.

Java

class Solution {
    private void nextTitle(StringBuilder title) {
        for (int i = title.length() - 1; i >= 0; i--) {
            if (title.charAt(i) == 'Z') {
                title.setCharAt(i, 'A');
            } else {
                title.setCharAt(i, (char) (title.charAt(i) + 1));
                return;
            }
        }
        title.insert(0, 'A');
    }

    public String convertToTitle(int columnNumber) {
        StringBuilder title = new StringBuilder("A");
        for (int i = 1; i < columnNumber; i++) {
            nextTitle(title);
        }
        return title.toString();
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.convertToTitle(1));
        System.out.println(s.convertToTitle(28));
        System.out.println(s.convertToTitle(701));
        System.out.println(s.convertToTitle(26));
        System.out.println(s.convertToTitle(703));
    }
}

Output

A
AB
ZY
Z
AAA

Time: O(n) amortized for column number n (a step usually changes one letter; carries are rare). Space: O(log n).

Optimal: bijective base 26

The titles form a base-26 system with no zero digit: the digits A..Z mean 1..26, which is why 26 is "Z" and not "BA". Subtracting 1 before each division turns the digits into 0..25. Repeat: n--, the last letter is (char) ('A' + n % 26), then n /= 26. Letters come out last to first, so reverse at the end.

For 28: n = 27, letter 27 % 26 = 1 is B, n = 1. Then n = 0, letter A, n = 0. Reversed: AB.

Java

class Solution {
    public String convertToTitle(int columnNumber) {
        StringBuilder letters = new StringBuilder();
        int n = columnNumber;
        while (n > 0) {
            n--;
            letters.append((char) ('A' + n % 26));
            n /= 26;
        }
        return letters.reverse().toString();
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.convertToTitle(1));
        System.out.println(s.convertToTitle(28));
        System.out.println(s.convertToTitle(701));
        System.out.println(s.convertToTitle(26));
        System.out.println(s.convertToTitle(703));
        System.out.println(s.convertToTitle(Integer.MAX_VALUE));
    }
}

Output

A
AB
ZY
Z
AAA
FXSHRXW

Time: O(log n). Space: O(log n) for the letters.

The n-- cannot go below zero because the loop only runs while n > 0. No intermediate value overflows int, since n only shrinks. The largest int input gives FXSHRXW, seven letters.