Tag: hashmap

3. Longest Substring Without Repeating Characters – Solution

Difficulty: medium
Topics: Hash Table, String, Sliding Window

Given a string s, find the length of the longest substring without repeating characters.

Example 1:
Input: s = “abcabcbb”
Output: 3
Explanation: The answer is “abc”, with the length of 3.

Example 2:
Input: s = “bbbbb”
Output: 1
Explanation: The answer is “b”, with the length of 1.

Example 3:
Input: s = “pwwkew”
Output: 3
Explanation: The answer is “wke”, with the length of 3. Notice that the answer must be a substring, “pwke” is a subsequence and not a substring.

Solution

It’s easy to come up with a O(n^2) approach. Just check the length of longest substring starting from 0 to end.

O(n) approach needs more thinking:

int lengthOfLongestSubstring(string s) {
        
        map<char, int> charMap;
        int start = -1;
        int maxLen = 0;
        
        for (int i = 0; i < s.size(); i++) {
            if (charMap.count(s[i]) != 0) {
                start = max(start, charMap[s[i]]);
            }
            charMap[s[i]] = i;
            maxLen = max(maxLen, i-start);
        }
        
        return maxLen;
    }

This puts the index of where characters appears in a hashmap. So as we iterate from 0 to end, we can know where that character appeared last time and find the length. Each time we recalculate the max.

Reflection

interesting concept to blackbox:

  • whenever finding a maximum value through iteration, let’s use maxval = max(maxval, newval)
  • use hashmap to store the value and its frequency, or value and index.
  • If the value is a character or linear sequence number, it can be stored in an array as well. But using hashmap can be more efficient space-wise.

1. Two Sum – Solution

Difficulty: Easy
Topics: Array, Hash Table

Question

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Example 1:Input: nums = [2,7,11,15], target = 9 Output: [0,1] Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:Input: nums = [3,2,4], target = 6 Output: [1,2]

Example 3:Input: nums = [3,3], target = 6 Output: [0,1]

Solution

While storing the numbers in hashmap, check if the complementary (target – number) is in the hashmap.

Note that hashmap[nums[i]] = i; should not be before the part where we search for comp. This is because search for comp should be done in values previously put in, not including the current value.

vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> hashmap;
        vector<int> res;
        for (int i = 0; i < nums.size(); i++){
            int comp = target - nums[i];
            if (hashmap.count(comp) > 0){
                res = {hashmap[comp], i};
                return res;
            }
            hashmap[nums[i]] = i;
        }
        return res;
    }

Hashmap in C++

Basic Usages

unordered_map<int, int> hashmap;
// 2. insert a new (key, value) pair
hashmap.insert(make_pair(2, 3));
// 3. insert a new (key, value) pair or update the value of existed key
hashmap[1] = 1;
hashmap[1] = 2;
// 4. get the value of a specific key
hashmap[1]
// 5. delete a key
hashmap.erase(2);
// 6. check if a key is in the hash map
if (hashmap.count(2) <= 0);
// 7. get the size of the hash map
hashmap.size() 
// 8. iterate the hash map
for (auto it = hashmap.begin(); it != hashmap.end(); ++it) {
    cout << it->first << "," << it->second << endl;
}
// 9. clear the hash map
hashmap.clear();
// 10. check if the hash map is empty
if (hashmap.empty())
Iterating over list of keys:
for (Type key : keys) {
        if (hashmap.count(key) > 0) {
            if (hashmap[key] satisfies the requirement) {
                return needed_information;
            }
        }
        // Value can be any information you needed (e.g. index)
        hashmap[key] = value;
    }

(to be continued…)

Iterating over map
for (auto& it : myMap) {
        vec.push_back(it);
    }
Sorting map based on value
#include <iostream>
#include <map>
#include <vector>
#include <algorithm>

// Comparator function to sort pairs by second value
bool sortByVal(const std::pair<int, int>& a, const std::pair<int, int>& b) {
    return (a.second < b.second);
}

int main() {
    // Define a map
    std::map<int, int> myMap = {{1, 40}, {2, 30}, {3, 60}, {4, 20}};

    // Copy elements to a vector of pairs
    std::vector<std::pair<int, int>> vec;
    for (auto& it : myMap) {
        vec.push_back(it);
    }

    // Sort the vector by value
    std::sort(vec.begin(), vec.end(), sortByVal);

    // Print the sorted vector
    for (auto& it : vec) {
        std::cout << it.first << ": " << it.second << std::endl;
    }

    return 0;
}

Tips

  • When counting frequency, don’t need to check if the hashmap[x] exists.
// don't do this:
if (hashmap.count(x) > 0) hashmap[x]++;
else hashmap[x] = 1;
// do this:
hashmap[x]++;

// same for adding up the frequency:
for (...){
   sum += hashmap[x];
}