Transform string to hash map

Question

Given a string, transform it into a hash map where each unique character in the string is a key, and the value is the count of occurrences of that character. The function should take the input string and return the resulting hash map. Ensure that the solution efficiently handles large strings and edge cases, such as empty strings or strings with special characters.

Codemia · Accepted Answer

The problem requires us to create a hash map (or dictionary in Python) that counts the occurrences of each unique character in a given string. This directly suggests the use of a hash map because it allows for efficient insertion and retrieval of counts based on the characters as keys. Each character's count can be updated in constant time, O(1), making this approach very efficient. The problem does not require sorting or searching through the string; instead, it's focused on counting, which is best suited for a hash map.

1. Initialize an empty dictionary to serve as our hash map. 
2. Iterate through each character in the input string: 
   - For each character, check if it is already a key in the hash map. 
   - If it is, increment its count by 1. 
   - If it isn't, add it to the hash map with a count of 1. 
3. After iterating through the string, return the completed hash map.

**Example:** For the input string 'hello', the iteration would proceed as follows: 
- 'h': Add to hash map -> {'h': 1} 
- 'e': Add to hash map -> {'h': 1, 'e': 1} 
- 'l': Add to hash map -> {'h': 1, 'e': 1, 'l': 1} 
- 'l': Increment count -> {'h': 1, 'e': 1, 'l': 2} 
- 'o': Add to hash map -> {'h': 1, 'e': 1, 'l': 2, 'o': 1} 
Final output would be: {'h': 1, 'e': 1, 'l': 2, 'o': 1}.

Here is the Python code that implements the above approach:

```python
def transform_string_to_hash_map(s):
    char_count = {}
    for char in s:
        if char in char_count:
            char_count[char] += 1
        else:
            char_count[char] = 1
    return char_count
```

This function takes a string `s` and returns a dictionary where each unique character is a key and its value is the count of occurrences in the string.

The time complexity of this solution is O(n), where n is the length of the input string. Each character is processed exactly once, with constant time operations for updating the hash map. The space complexity is O(k), where k is the number of unique characters in the string. In the worst case, k could be equal to n (if all characters are unique), but typically k will be much smaller, especially with larger character sets.

1. **Empty String:** If the input string is empty, the function should return an empty dictionary: `transform_string_to_hash_map('')` returns `{}`.
2. **String with Special Characters:** The function should handle strings with special characters and spaces, e.g., `transform_string_to_hash_map('a!b@c#')` should return `{'a': 1, '!': 1, 'b': 1, '@': 1, 'c': 1, '#': 1}`.
3. **Case Sensitivity:** The function is case-sensitive, meaning 'A' and 'a' will be treated as different keys: `transform_string_to_hash_map('Aa')` returns `{'A': 1, 'a': 1}`.

Transform string to hash map

Bloomberg

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Problem Analysis

Approach

Submit Your Answer

Bloomberg Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string