Problem

Yesterday you implemented a function that encodes a hexadecimal string into Base64.

Write a function to decode a Base64 string back to a hexadecimal string.

For example, the following string:

1

3q2+7w==

should produce:

1

deadbeef

Examples

Example 1

1
2
3

Input: "3q2+7w=="
Output: "deadbeef"
Explanation: The base64 string "3q2+7w==" decodes to bytes [0xde, 0xad, 0xbe, 0xef]. Converting to hex produces "deadbeef".

Example 2

1
2
3

Input: "SGVsbG8="
Output: "48656c6c6f"
Explanation: The base64 string "SGVsbG8=" decodes to "Hello" in ASCII. Converting each byte to hex: H→48, e→65, l→6c, l→6c, o→6f.

Example 3

1
2
3

Input: "QQ=="
Output: "41"
Explanation: Base64 "QQ==" with two padding characters decodes to single byte 0x41 (65 decimal, 'A' in ASCII).

Example 4

1
2
3

Input: "QUI="
Output: "4142"
Explanation: Base64 "QUI=" with one padding character decodes to two bytes 0x41, 0x42 ("AB" in ASCII).

Example 5

1
2
3

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

Example 6

1
2
3

Input: "QUJD"
Output: "414243"
Explanation: Base64 "QUJD" with no padding decodes to three bytes 0x41, 0x42, 0x43 ("ABC" in ASCII).

Example 7

1
2
3

Input: "YWJjZGVmZ2hpams="
Output: "6162636465666768696a6b"
Explanation: Base64 string decodes to "abcdefghijk" in ASCII, then converted to hex representation.

Solution

Method 1 - Direct Base64 Decoding

Intuition

Base64 decoding reverses the encoding process: each group of 4 base64 characters (6 bits each, 24 bits total) converts back to 3 bytes (8 bits each). We need to map each base64 character to its 6-bit value, combine groups of 4 characters, extract the resulting bytes, and convert each byte to its 2-character hex representation. Padding characters (’=’) indicate fewer than 3 output bytes.

Approach

  1. Handle Empty Input: Return empty string for empty base64 input
  2. Create Lookup Table: Map each base64 character to its 6-bit value (0-63)
  3. Remove Padding: Count and remove ‘=’ padding characters from end
  4. Process Groups: Convert every 4 base64 characters to 3 bytes
  5. Bit Manipulation: Combine 4×6-bit values into 3×8-bit bytes
  6. Handle Partial Groups: Process remaining characters based on padding count
  7. Convert to Hex: Convert each byte to 2-character lowercase hex string
  8. Return Result: Concatenate all hex pairs into final 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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

class Solution {
public:
    string base64ToHex(string base64) {
        if (base64.empty()) return "";
        
        // Base64 character to value mapping
        unordered_map<char, int> charMap;
        string chars = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
        for (int i = 0; i < chars.length(); i++) {
            charMap[chars[i]] = i;
        }
        
        // Remove padding and count it
        int padding = 0;
        while (!base64.empty() && base64.back() == '=') {
            base64.pop_back();
            padding++;
        }
        
        vector<uint8_t> bytes;
        
        // Process groups of 4 characters
        for (int i = 0; i < base64.length(); i += 4) {
            uint32_t group = 0;
            int validChars = min(4, (int)base64.length() - i);
            
            // Combine 4 base64 chars into 24-bit group
            for (int j = 0; j < validChars; j++) {
                group = (group << 6) | charMap[base64[i + j]];
            }
            
            // Shift for incomplete groups
            for (int j = validChars; j < 4; j++) {
                group <<= 6;
            }
            
            // Extract bytes (up to 3 depending on padding)
            int bytesToExtract = 3 - padding;
            if (i + 4 >= base64.length()) {
                // Last group - adjust for padding
                if (validChars == 2) bytesToExtract = 1;
                else if (validChars == 3) bytesToExtract = 2;
                else if (validChars == 4) bytesToExtract = 3;
            } else {
                bytesToExtract = 3; // Full group
            }
            
            for (int j = 0; j < bytesToExtract; j++) {
                bytes.push_back((group >> (16 - j * 8)) & 0xFF);
            }
        }
        
        // Convert bytes to hex
        string ans = "";
        for (uint8_t byte : bytes) {
            char hex[3];
            sprintf(hex, "%02x", byte);
            ans += hex;
        }
        
        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
65
66

func Base64ToHex(base64 string) string {
    if len(base64) == 0 {
        return ""
    }
    
    // Create character mapping
    charMap := make(map[byte]int)
    chars := "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/"
    for i, c := range chars {
        charMap[byte(c)] = i
    }
    
    // Remove padding
    padding := 0
    for len(base64) > 0 && base64[len(base64)-1] == '=' {
        base64 = base64[:len(base64)-1]
        padding++
    }
    
    var bytes []byte
    
    // Process groups of 4 characters
    for i := 0; i < len(base64); i += 4 {
        var group uint32
        validChars := min(4, len(base64)-i)
        
        // Combine chars into 24-bit group
        for j := 0; j < validChars; j++ {
            group = (group << 6) | uint32(charMap[base64[i+j]])
        }
        
        // Shift for incomplete groups
        for j := validChars; j < 4; j++ {
            group <<= 6
        }
        
        // Extract bytes
        bytesToExtract := 3
        if i+4 >= len(base64) {
            if validChars == 2 {
                bytesToExtract = 1
            } else if validChars == 3 {
                bytesToExtract = 2
            }
        }
        
        for j := 0; j < bytesToExtract; j++ {
            bytes = append(bytes, byte((group>>(16-j*8))&0xFF))
        }
    }
    
    // Convert to hex
    var ans strings.Builder
    for _, b := range bytes {
        ans.WriteString(fmt.Sprintf("%02x", b))
    }
    
    return ans.String()
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}
 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

class Solution {
    public String base64ToHex(String base64) {
        if (base64.isEmpty()) return "";
        
        // Create character mapping
        Map<Character, Integer> charMap = new HashMap<>();
        String chars = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
        for (int i = 0; i < chars.length(); i++) {
            charMap.put(chars.charAt(i), i);
        }
        
        // Remove padding
        int padding = 0;
        while (!base64.isEmpty() && base64.charAt(base64.length() - 1) == '=') {
            base64 = base64.substring(0, base64.length() - 1);
            padding++;
        }
        
        List<Byte> bytes = new ArrayList<>();
        
        // Process groups of 4 characters
        for (int i = 0; i < base64.length(); i += 4) {
            int group = 0;
            int validChars = Math.min(4, base64.length() - i);
            
            // Combine chars into 24-bit group
            for (int j = 0; j < validChars; j++) {
                group = (group << 6) | charMap.get(base64.charAt(i + j));
            }
            
            // Shift for incomplete groups
            for (int j = validChars; j < 4; j++) {
                group <<= 6;
            }
            
            // Extract bytes
            int bytesToExtract = 3;
            if (i + 4 >= base64.length()) {
                if (validChars == 2) bytesToExtract = 1;
                else if (validChars == 3) bytesToExtract = 2;
            }
            
            for (int j = 0; j < bytesToExtract; j++) {
                bytes.add((byte)((group >> (16 - j * 8)) & 0xFF));
            }
        }
        
        // Convert to hex
        StringBuilder ans = new StringBuilder();
        for (byte b : bytes) {
            ans.append(String.format("%02x", b & 0xFF));
        }
        
        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

class Solution:
    def base64ToHex(self, base64: str) -> str:
        if not base64:
            return ""
        
        # Create character mapping
        chars = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/"
        char_map = {c: i for i, c in enumerate(chars)}
        
        # Remove padding
        padding = 0
        while base64 and base64[-1] == '=':
            base64 = base64[:-1]
            padding += 1
        
        bytes_data = []
        
        # Process groups of 4 characters
        for i in range(0, len(base64), 4):
            group = 0
            valid_chars = min(4, len(base64) - i)
            
            # Combine chars into 24-bit group
            for j in range(valid_chars):
                group = (group << 6) | char_map[base64[i + j]]
            
            # Shift for incomplete groups
            for j in range(valid_chars, 4):
                group <<= 6
            
            # Extract bytes
            bytes_to_extract = 3
            if i + 4 >= len(base64):
                if valid_chars == 2:
                    bytes_to_extract = 1
                elif valid_chars == 3:
                    bytes_to_extract = 2
            
            for j in range(bytes_to_extract):
                bytes_data.append((group >> (16 - j * 8)) & 0xFF)
        
        # Convert to hex
        ans = ""
        for byte_val in bytes_data:
            ans += f"{byte_val:02x}"
        
        return ans

Complexity

  • ⏰ Time complexity: O(n) where n is the length of the base64 string, as we process each character once and perform constant time operations for each group.
  • 🧺 Space complexity: O(n) for storing the character mapping, byte array, and resulting hex string.

Method 2 - Optimized Lookup Array

Intuition

We can optimize the decoding by using a direct lookup array instead of a hash map for base64 character-to-value mapping. Since base64 characters have known ASCII values, we can create a 128-element array for O(1) lookups. Additionally, we can process the string more efficiently by avoiding string modifications and calculating padding without actually removing characters.

Approach

  1. Create Direct Lookup: Use ASCII-indexed array for O(1) base64 character mapping
  2. Count Padding: Calculate padding without modifying the input string
  3. Efficient Processing: Process characters in-place without string operations
  4. Optimized Bit Operations: Use more efficient bit manipulation techniques
  5. Batch Hex Conversion: Convert bytes to hex more efficiently
  6. Memory Optimization: Pre-allocate result string to avoid reallocations
  7. Edge Case Handling: Handle invalid characters and malformed input gracefully

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
64

class Solution {
private:
    vector<int> createLookupTable() {
        vector<int> lookup(128, -1);
        string chars = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
        for (int i = 0; i < chars.length(); i++) {
            lookup[chars[i]] = i;
        }
        return lookup;
    }
    
public:
    string base64ToHexOptimized(string base64) {
        if (base64.empty()) return "";
        
        static vector<int> lookup = createLookupTable();
        
        // Count padding without modifying string
        int padding = 0;
        int len = base64.length();
        while (len > 0 && base64[len - 1] == '=') {
            len--;
            padding++;
        }
        
        // Pre-calculate result size
        int byteCount = (len * 6) / 8;
        string ans;
        ans.reserve(byteCount * 2);
        
        vector<uint8_t> bytes;
        bytes.reserve(byteCount);
        
        // Process groups more efficiently
        for (int i = 0; i < len; i += 4) {
            uint32_t group = 0;
            int validChars = min(4, len - i);
            
            // Process valid characters
            for (int j = 0; j < validChars; j++) {
                int val = lookup[base64[i + j]];
                group = (group << 6) | val;
            }
            
            // Shift remaining positions
            group <<= (4 - validChars) * 6;
            
            // Extract bytes based on valid chars
            int bytesToExtract = min(3, (validChars * 6) / 8);
            for (int j = 0; j < bytesToExtract; j++) {
                bytes.push_back((group >> (16 - j * 8)) & 0xFF);
            }
        }
        
        // Optimized hex conversion
        static const char hexChars[] = "0123456789abcdef";
        for (uint8_t byte : bytes) {
            ans += hexChars[byte >> 4];
            ans += hexChars[byte & 0x0F];
        }
        
        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

func Base64ToHexOptimized(base64 string) string {
    if len(base64) == 0 {
        return ""
    }
    
    // Create lookup array
    lookup := make([]int, 128)
    for i := range lookup {
        lookup[i] = -1
    }
    chars := "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/"
    for i, c := range chars {
        lookup[c] = i
    }
    
    // Count padding
    length := len(base64)
    for length > 0 && base64[length-1] == '=' {
        length--
    }
    
    // Pre-calculate capacity
    byteCount := (length * 6) / 8
    bytes := make([]byte, 0, byteCount)
    
    // Process groups
    for i := 0; i < length; i += 4 {
        var group uint32
        validChars := min(4, length-i)
        
        for j := 0; j < validChars; j++ {
            val := lookup[base64[i+j]]
            group = (group << 6) | uint32(val)
        }
        
        group <<= uint32((4 - validChars) * 6)
        
        bytesToExtract := min(3, (validChars*6)/8)
        for j := 0; j < bytesToExtract; j++ {
            bytes = append(bytes, byte((group>>(16-j*8))&0xFF))
        }
    }
    
    // Optimized hex conversion
    var ans strings.Builder
    ans.Grow(len(bytes) * 2)
    hexChars := "0123456789abcdef"
    
    for _, b := range bytes {
        ans.WriteByte(hexChars[b>>4])
        ans.WriteByte(hexChars[b&0x0F])
    }
    
    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

class Solution {
    private static final int[] LOOKUP = new int[128];
    
    static {
        Arrays.fill(LOOKUP, -1);
        String chars = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
        for (int i = 0; i < chars.length(); i++) {
            LOOKUP[chars.charAt(i)] = i;
        }
    }
    
    public String base64ToHexOptimized(String base64) {
        if (base64.isEmpty()) return "";
        
        // Count padding
        int length = base64.length();
        while (length > 0 && base64.charAt(length - 1) == '=') {
            length--;
        }
        
        // Pre-calculate capacity
        int byteCount = (length * 6) / 8;
        List<Byte> bytes = new ArrayList<>(byteCount);
        
        // Process groups
        for (int i = 0; i < length; i += 4) {
            int group = 0;
            int validChars = Math.min(4, length - i);
            
            for (int j = 0; j < validChars; j++) {
                int val = LOOKUP[base64.charAt(i + j)];
                group = (group << 6) | val;
            }
            
            group <<= (4 - validChars) * 6;
            
            int bytesToExtract = Math.min(3, (validChars * 6) / 8);
            for (int j = 0; j < bytesToExtract; j++) {
                bytes.add((byte)((group >> (16 - j * 8)) & 0xFF));
            }
        }
        
        // Optimized hex conversion
        StringBuilder ans = new StringBuilder(bytes.size() * 2);
        final char[] hexChars = "0123456789abcdef".toCharArray();
        
        for (byte b : bytes) {
            int val = b & 0xFF;
            ans.append(hexChars[val >> 4]);
            ans.append(hexChars[val & 0x0F]);
        }
        
        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

class Solution:
    def __init__(self):
        # Pre-compute lookup table
        self.lookup = [-1] * 128
        chars = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/"
        for i, c in enumerate(chars):
            self.lookup[ord(c)] = i
        
        self.hex_chars = "0123456789abcdef"
    
    def base64ToHexOptimized(self, base64: str) -> str:
        if not base64:
            return ""
        
        # Count padding
        length = len(base64)
        while length > 0 and base64[length - 1] == '=':
            length -= 1
        
        bytes_data = []
        
        # Process groups
        for i in range(0, length, 4):
            group = 0
            valid_chars = min(4, length - i)
            
            for j in range(valid_chars):
                val = self.lookup[ord(base64[i + j])]
                group = (group << 6) | val
            
            group <<= (4 - valid_chars) * 6
            
            bytes_to_extract = min(3, (valid_chars * 6) // 8)
            for j in range(bytes_to_extract):
                bytes_data.append((group >> (16 - j * 8)) & 0xFF)
        
        # Optimized hex conversion
        ans = []
        for byte_val in bytes_data:
            ans.append(self.hex_chars[byte_val >> 4])
            ans.append(self.hex_chars[byte_val & 0x0F])
        
        return ''.join(ans)
    
    def base64ToHexBuiltin(self, base64: str) -> str:
        if not base64:
            return ""
        
        # Alternative using Python's built-in base64 decoding
        import base64 as b64
        try:
            # Add padding if needed
            missing_padding = len(base64) % 4
            if missing_padding:
                base64 += '=' * (4 - missing_padding)
            
            decoded_bytes = b64.b64decode(base64)
            return decoded_bytes.hex()
        except:
            # Fallback to manual implementation
            return self.base64ToHexOptimized(base64)

Complexity

  • ⏰ Time complexity: O(n) where n is the length of the base64 string, with improved constant factors due to lookup array optimization and efficient string building.
  • 🧺 Space complexity: O(1) for the fixed-size lookup table plus O(n) for the output, with optimized memory allocation reducing overhead.