Problem

Read this Wikipedia article on Base64 encoding.

Implement a function that converts a hex string to base64.

For example, the string:

1

deadbeef

should produce:

1

3q2+7w==

Examples

Example 1

1
2
3

Input: "deadbeef"
Output: "3q2+7w=="
Explanation: The hex string "deadbeef" represents bytes [0xde, 0xad, 0xbe, 0xef]. Converting to base64: 222,173,190,239 → groups of 6 bits → base64 characters "3q2+7w==".

Example 2

1
2
3

Input: "48656c6c6f"
Output: "SGVsbG8="
Explanation: The hex string "48656c6c6f" represents "Hello" in ASCII. Converting each pair: 48→H, 65→e, 6c→l, 6c→l, 6f→o. Base64 encoding produces "SGVsbG8=".

Example 3

1
2
3

Input: "41"
Output: "QQ=="
Explanation: Single hex byte "41" represents 'A' in ASCII (65 decimal). Base64 encoding with padding produces "QQ==".

Example 4

1
2
3

Input: "4142"
Output: "QUI="
Explanation: Two hex bytes "4142" represent "AB" in ASCII. Base64 encoding with one padding character produces "QUI=".

Example 5

1
2
3

Input: ""
Output: ""
Explanation: Empty hex string produces empty base64 string.

Example 6

1
2
3

Input: "414243"
Output: "QUJD"
Explanation: Three hex bytes "414243" represent "ABC" in ASCII. Base64 encoding with no padding needed produces "QUJD".

Solution

Method 1 - Direct Bit Manipulation

Intuition

Base64 encoding works by converting every 3 bytes (24 bits) into 4 base64 characters (6 bits each). To convert hex to base64, we first convert hex pairs to bytes, then group these bytes and extract 6-bit chunks to map to base64 characters. The key insight is that hex represents binary data in a human-readable format, and base64 is another encoding of that same binary data.

Approach

  1. Parse Hex String: Convert each pair of hex characters to a byte value
  2. Handle Empty Input: Return empty string for empty hex input
  3. Group into Bytes: Process hex string in pairs (each pair = 1 byte)
  4. Convert to Binary: Each byte becomes 8 bits of binary data
  5. Group by 6 bits: Extract 6-bit chunks from the binary stream
  6. Map to Base64: Convert each 6-bit value (0-63) to corresponding base64 character
  7. Add Padding: Add ‘=’ characters to make output length multiple of 4
  8. Return Result: Complete base64 encoded string

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

class Solution {
public:
    string hexToBase64(string hex) {
        if (hex.empty()) return "";
        
        const string chars = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
        vector<uint8_t> bytes;
        
        // Convert hex to bytes
        for (int i = 0; i < hex.length(); i += 2) {
            string hexPair = hex.substr(i, 2);
            bytes.push_back(stoi(hexPair, nullptr, 16));
        }
        
        string ans = "";
        int i = 0;
        
        // Process 3 bytes at a time
        while (i + 2 < bytes.size()) {
            uint32_t group = (bytes[i] << 16) | (bytes[i+1] << 8) | bytes[i+2];
            ans += chars[(group >> 18) & 63];
            ans += chars[(group >> 12) & 63];
            ans += chars[(group >> 6) & 63];
            ans += chars[group & 63];
            i += 3;
        }
        
        // Handle remaining bytes with padding
        if (i < bytes.size()) {
            uint32_t group = bytes[i] << 16;
            if (i + 1 < bytes.size()) group |= bytes[i+1] << 8;
            
            ans += chars[(group >> 18) & 63];
            ans += chars[(group >> 12) & 63];
            
            if (i + 1 < bytes.size()) {
                ans += chars[(group >> 6) & 63];
                ans += "=";
            } else {
                ans += "==";
            }
        }
        
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

func HexToBase64(hex string) string {
    if len(hex) == 0 {
        return ""
    }
    
    chars := "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/"
    var bytes []byte
    
    // Convert hex to bytes
    for i := 0; i < len(hex); i += 2 {
        hexPair := hex[i:i+2]
        val, _ := strconv.ParseUint(hexPair, 16, 8)
        bytes = append(bytes, byte(val))
    }
    
    var ans strings.Builder
    i := 0
    
    // Process 3 bytes at a time
    for i+2 < len(bytes) {
        group := uint32(bytes[i])<<16 | uint32(bytes[i+1])<<8 | uint32(bytes[i+2])
        ans.WriteByte(chars[(group>>18)&63])
        ans.WriteByte(chars[(group>>12)&63])
        ans.WriteByte(chars[(group>>6)&63])
        ans.WriteByte(chars[group&63])
        i += 3
    }
    
    // Handle remaining bytes with padding
    if i < len(bytes) {
        group := uint32(bytes[i]) << 16
        if i+1 < len(bytes) {
            group |= uint32(bytes[i+1]) << 8
        }
        
        ans.WriteByte(chars[(group>>18)&63])
        ans.WriteByte(chars[(group>>12)&63])
        
        if i+1 < len(bytes) {
            ans.WriteByte(chars[(group>>6)&63])
            ans.WriteByte('=')
        } else {
            ans.WriteString("==")
        }
    }
    
    return ans.String()
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

class Solution {
    public String hexToBase64(String hex) {
        if (hex.isEmpty()) return "";
        
        String chars = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
        byte[] bytes = new byte[hex.length() / 2];
        
        // Convert hex to bytes
        for (int i = 0; i < hex.length(); i += 2) {
            String hexPair = hex.substring(i, i + 2);
            bytes[i / 2] = (byte) Integer.parseInt(hexPair, 16);
        }
        
        StringBuilder ans = new StringBuilder();
        int i = 0;
        
        // Process 3 bytes at a time
        while (i + 2 < bytes.length) {
            int group = ((bytes[i] & 0xFF) << 16) | ((bytes[i+1] & 0xFF) << 8) | (bytes[i+2] & 0xFF);
            ans.append(chars.charAt((group >> 18) & 63));
            ans.append(chars.charAt((group >> 12) & 63));
            ans.append(chars.charAt((group >> 6) & 63));
            ans.append(chars.charAt(group & 63));
            i += 3;
        }
        
        // Handle remaining bytes with padding
        if (i < bytes.length) {
            int group = (bytes[i] & 0xFF) << 16;
            if (i + 1 < bytes.length) group |= (bytes[i+1] & 0xFF) << 8;
            
            ans.append(chars.charAt((group >> 18) & 63));
            ans.append(chars.charAt((group >> 12) & 63));
            
            if (i + 1 < bytes.length) {
                ans.append(chars.charAt((group >> 6) & 63));
                ans.append("=");
            } else {
                ans.append("==");
            }
        }
        
        return ans.toString();
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

class Solution:
    def hexToBase64(self, hex: str) -> str:
        if not hex:
            return ""
        
        chars = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/"
        bytes_data = []
        
        # Convert hex to bytes
        for i in range(0, len(hex), 2):
            hex_pair = hex[i:i+2]
            bytes_data.append(int(hex_pair, 16))
        
        ans = ""
        i = 0
        
        # Process 3 bytes at a time
        while i + 2 < len(bytes_data):
            group = (bytes_data[i] << 16) | (bytes_data[i+1] << 8) | bytes_data[i+2]
            ans += chars[(group >> 18) & 63]
            ans += chars[(group >> 12) & 63]
            ans += chars[(group >> 6) & 63]
            ans += chars[group & 63]
            i += 3
        
        # Handle remaining bytes with padding
        if i < len(bytes_data):
            group = bytes_data[i] << 16
            if i + 1 < len(bytes_data):
                group |= bytes_data[i+1] << 8
            
            ans += chars[(group >> 18) & 63]
            ans += chars[(group >> 12) & 63]
            
            if i + 1 < len(bytes_data):
                ans += chars[(group >> 6) & 63]
                ans += "="
            else:
                ans += "=="
        
        return ans

Complexity

  • ⏰ Time complexity: O(n) where n is the length of the hex string, as we process each hex character once to convert to bytes and then process each byte once for base64 encoding.
  • 🧺 Space complexity: O(n) for storing the byte array and the resulting base64 string.

Method 2 - Lookup Table Optimization

Intuition

We can optimize the conversion by pre-computing lookup tables for hex-to-byte conversion and avoiding repeated string operations. This method uses the same algorithmic approach but with better constant factors through optimized data structures and batch processing of bits.

Approach

  1. Pre-compute Lookup: Create hex digit to value mapping for O(1) conversion
  2. Batch Processing: Convert all hex to bytes first, then process base64 encoding
  3. Bit Manipulation: Use efficient bit shifting and masking operations
  4. String Builder: Use StringBuilder/similar for efficient string concatenation
  5. Optimize Padding: Handle padding logic with minimal branching
  6. Memory Efficiency: Minimize intermediate data structure allocations
  7. Return Optimized: Use optimized string building techniques

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

class Solution {
private:
    const string BASE64_CHARS = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
    
    int hexCharToInt(char c) {
        if (c >= '0' && c <= '9') return c - '0';
        if (c >= 'a' && c <= 'f') return c - 'a' + 10;
        if (c >= 'A' && c <= 'F') return c - 'A' + 10;
        return 0;
    }
    
public:
    string hexToBase64Optimized(string hex) {
        if (hex.empty()) return "";
        
        int byteCount = hex.length() / 2;
        vector<uint8_t> bytes;
        bytes.reserve(byteCount);
        
        // Convert hex to bytes using lookup
        for (int i = 0; i < hex.length(); i += 2) {
            uint8_t byte = (hexCharToInt(hex[i]) << 4) | hexCharToInt(hex[i+1]);
            bytes.push_back(byte);
        }
        
        string ans;
        ans.reserve((byteCount + 2) / 3 * 4); // Pre-allocate exact size needed
        
        int i = 0;
        // Process complete 3-byte groups
        while (i + 2 < bytes.size()) {
            uint32_t triplet = (uint32_t(bytes[i]) << 16) | 
                              (uint32_t(bytes[i+1]) << 8) | 
                              uint32_t(bytes[i+2]);
            
            ans += BASE64_CHARS[(triplet >> 18) & 0x3F];
            ans += BASE64_CHARS[(triplet >> 12) & 0x3F];
            ans += BASE64_CHARS[(triplet >> 6) & 0x3F];
            ans += BASE64_CHARS[triplet & 0x3F];
            i += 3;
        }
        
        // Handle remaining 1 or 2 bytes
        if (i < bytes.size()) {
            uint32_t triplet = uint32_t(bytes[i]) << 16;
            if (i + 1 < bytes.size()) {
                triplet |= uint32_t(bytes[i+1]) << 8;
            }
            
            ans += BASE64_CHARS[(triplet >> 18) & 0x3F];
            ans += BASE64_CHARS[(triplet >> 12) & 0x3F];
            
            if (i + 1 < bytes.size()) {
                ans += BASE64_CHARS[(triplet >> 6) & 0x3F];
                ans += '=';
            } else {
                ans += "==";
            }
        }
        
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

func HexToBase64Optimized(hex string) string {
    if len(hex) == 0 {
        return ""
    }
    
    const base64Chars = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/"
    
    hexCharToInt := func(c byte) int {
        switch {
        case c >= '0' && c <= '9':
            return int(c - '0')
        case c >= 'a' && c <= 'f':
            return int(c - 'a' + 10)
        case c >= 'A' && c <= 'F':
            return int(c - 'A' + 10)
        default:
            return 0
        }
    }
    
    byteCount := len(hex) / 2
    bytes := make([]byte, 0, byteCount)
    
    // Convert hex to bytes
    for i := 0; i < len(hex); i += 2 {
        b := byte((hexCharToInt(hex[i]) << 4) | hexCharToInt(hex[i+1]))
        bytes = append(bytes, b)
    }
    
    var ans strings.Builder
    ans.Grow((byteCount + 2) / 3 * 4) // Pre-allocate capacity
    
    i := 0
    // Process complete 3-byte groups
    for i+2 < len(bytes) {
        triplet := uint32(bytes[i])<<16 | uint32(bytes[i+1])<<8 | uint32(bytes[i+2])
        
        ans.WriteByte(base64Chars[(triplet>>18)&0x3F])
        ans.WriteByte(base64Chars[(triplet>>12)&0x3F])
        ans.WriteByte(base64Chars[(triplet>>6)&0x3F])
        ans.WriteByte(base64Chars[triplet&0x3F])
        i += 3
    }
    
    // Handle remaining bytes
    if i < len(bytes) {
        triplet := uint32(bytes[i]) << 16
        if i+1 < len(bytes) {
            triplet |= uint32(bytes[i+1]) << 8
        }
        
        ans.WriteByte(base64Chars[(triplet>>18)&0x3F])
        ans.WriteByte(base64Chars[(triplet>>12)&0x3F])
        
        if i+1 < len(bytes) {
            ans.WriteByte(base64Chars[(triplet>>6)&0x3F])
            ans.WriteByte('=')
        } else {
            ans.WriteString("==")
        }
    }
    
    return ans.String()
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

class Solution {
    private static final String BASE64_CHARS = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
    
    private int hexCharToInt(char c) {
        if (c >= '0' && c <= '9') return c - '0';
        if (c >= 'a' && c <= 'f') return c - 'a' + 10;
        if (c >= 'A' && c <= 'F') return c - 'A' + 10;
        return 0;
    }
    
    public String hexToBase64Optimized(String hex) {
        if (hex.isEmpty()) return "";
        
        int byteCount = hex.length() / 2;
        byte[] bytes = new byte[byteCount];
        
        // Convert hex to bytes using optimized parsing
        for (int i = 0, j = 0; i < hex.length(); i += 2, j++) {
            bytes[j] = (byte)((hexCharToInt(hex.charAt(i)) << 4) | hexCharToInt(hex.charAt(i+1)));
        }
        
        StringBuilder ans = new StringBuilder((byteCount + 2) / 3 * 4);
        
        int i = 0;
        // Process complete 3-byte groups
        while (i + 2 < bytes.length) {
            int triplet = ((bytes[i] & 0xFF) << 16) | 
                         ((bytes[i+1] & 0xFF) << 8) | 
                         (bytes[i+2] & 0xFF);
            
            ans.append(BASE64_CHARS.charAt((triplet >> 18) & 0x3F));
            ans.append(BASE64_CHARS.charAt((triplet >> 12) & 0x3F));
            ans.append(BASE64_CHARS.charAt((triplet >> 6) & 0x3F));
            ans.append(BASE64_CHARS.charAt(triplet & 0x3F));
            i += 3;
        }
        
        // Handle remaining bytes
        if (i < bytes.length) {
            int triplet = (bytes[i] & 0xFF) << 16;
            if (i + 1 < bytes.length) {
                triplet |= (bytes[i+1] & 0xFF) << 8;
            }
            
            ans.append(BASE64_CHARS.charAt((triplet >> 18) & 0x3F));
            ans.append(BASE64_CHARS.charAt((triplet >> 12) & 0x3F));
            
            if (i + 1 < bytes.length) {
                ans.append(BASE64_CHARS.charAt((triplet >> 6) & 0x3F));
                ans.append('=');
            } else {
                ans.append("==");
            }
        }
        
        return ans.toString();
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86

class Solution:
    def __init__(self):
        self.BASE64_CHARS = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/"
        # Pre-compute hex lookup table for O(1) conversion
        self.hex_lookup = {
            '0': 0, '1': 1, '2': 2, '3': 3, '4': 4, '5': 5, '6': 6, '7': 7,
            '8': 8, '9': 9, 'a': 10, 'b': 11, 'c': 12, 'd': 13, 'e': 14, 'f': 15,
            'A': 10, 'B': 11, 'C': 12, 'D': 13, 'E': 14, 'F': 15
        }
    
    def hexToBase64Optimized(self, hex: str) -> str:
        if not hex:
            return ""
        
        # Convert hex to bytes using lookup table
        bytes_data = []
        for i in range(0, len(hex), 2):
            byte_val = (self.hex_lookup[hex[i]] << 4) | self.hex_lookup[hex[i+1]]
            bytes_data.append(byte_val)
        
        ans = []
        i = 0
        
        # Process complete 3-byte groups
        while i + 2 < len(bytes_data):
            triplet = (bytes_data[i] << 16) | (bytes_data[i+1] << 8) | bytes_data[i+2]
            
            ans.append(self.BASE64_CHARS[(triplet >> 18) & 0x3F])
            ans.append(self.BASE64_CHARS[(triplet >> 12) & 0x3F])
            ans.append(self.BASE64_CHARS[(triplet >> 6) & 0x3F])
            ans.append(self.BASE64_CHARS[triplet & 0x3F])
            i += 3
        
        # Handle remaining bytes
        if i < len(bytes_data):
            triplet = bytes_data[i] << 16
            if i + 1 < len(bytes_data):
                triplet |= bytes_data[i+1] << 8
            
            ans.append(self.BASE64_CHARS[(triplet >> 18) & 0x3F])
            ans.append(self.BASE64_CHARS[(triplet >> 12) & 0x3F])
            
            if i + 1 < len(bytes_data):
                ans.append(self.BASE64_CHARS[(triplet >> 6) & 0x3F])
                ans.append('=')
            else:
                ans.append('==')
        
        return ''.join(ans)
    
    def hexToBase64BytesMethod(self, hex: str) -> str:
        if not hex:
            return ""
        
        # Alternative using Python's built-in bytes conversion
        bytes_data = bytes.fromhex(hex)
        
        ans = []
        i = 0
        
        while i + 2 < len(bytes_data):
            triplet = (bytes_data[i] << 16) | (bytes_data[i+1] << 8) | bytes_data[i+2]
            
            ans.extend([
                self.BASE64_CHARS[(triplet >> 18) & 0x3F],
                self.BASE64_CHARS[(triplet >> 12) & 0x3F],
                self.BASE64_CHARS[(triplet >> 6) & 0x3F],
                self.BASE64_CHARS[triplet & 0x3F]
            ])
            i += 3
        
        if i < len(bytes_data):
            triplet = bytes_data[i] << 16
            if i + 1 < len(bytes_data):
                triplet |= bytes_data[i+1] << 8
            
            ans.append(self.BASE64_CHARS[(triplet >> 18) & 0x3F])
            ans.append(self.BASE64_CHARS[(triplet >> 12) & 0x3F])
            
            if i + 1 < len(bytes_data):
                ans.append(self.BASE64_CHARS[(triplet >> 6) & 0x3F])
                ans.append('=')
            else:
                ans.extend(['=', '='])
        
        return ''.join(ans)

Complexity

  • ⏰ Time complexity: O(n) where n is the length of the hex string, with improved constant factors due to lookup table optimization and pre-allocated string builders.
  • 🧺 Space complexity: O(n) for the byte array and result string, with optimized memory allocation reducing overhead from repeated string concatenations.