Hashmap

Intro

HashMap are great solutions for O(1) lookup and O(1) insertion (typically, but sometimes a freak case may be O(n)) . Because of this, they’re great for keeping track of values and their positions in data structures.

Longest Substring Without Repeating Characters - Medium

This is a typical programming problem, however note that a Substring is NOT the same as a Subsequence! The idea for this problem is to have a sliding “window” of sorts, implemented by two pointers, the start of your substring and the end (current index as you iterate through). Along the way use a HashMap to track the letters and their locations and an integer to track the maxLength of said window.

1. When a repeat character is found by checking if it’s in the hashmap, update the start pointer to be the max of either the last position of the character or current index.
2. Then update the position of the current char in the map.
3. Update the maxLength to be the max of either end - left + 1 or itself. I,e, if end - left + 1 is greater then update.

class Solution { 
	public int lengthOfLongestSubstring(String s) { 
		HashMap<Character, Integer> mapsy = new HashMap();
		int start = 0; int maxLength = 0;
		for(int end = 0; end < s.length(); end++){
			Character current = s.charAt(end);
			if(mapsy.containsKey(current)){
				int prev = mapsy.get(current);
				start = (prev + 1 > start) ? prev + 1 : start;
			}
			// updates location of the char in the map
			mapsy.put(current, end);
			maxLength = ((end - start + 1) > maxLength) ? (end - start + 1) : maxLength;
		}
		 return maxLength;
	}
}

// Side note, I feel like you could do this with a Set as well but you’d lose the positions of the characters…

Ransom Note - Easy

This is the naive and simplistic way of solving this problem, nothing wrong with it just a bit heavy on memory.

Breakdown

• Init your map/hashmap with characters as keys and integers as values
• Go through the magazine string and count the characters’ frequencies storing them in the map.
• Go through the note’s characters and check values, if greater than or equal to 1 then decrement, otherwise bingo!

Code:

public boolean canConstruct(String ransomNote, String magazine) {
         HashMap<Character, Integer> magChars = new HashMap<>();
 
        for (char c : magazine.toCharArray()) {
            if(magChars.containsKey(c)){
                magChars.put(c, magChars.get(c) + 1);
            }
            else{
                magChars.put(c, 1);
            }
        }
 
        for (char i: ransomNote.toCharArray()) {
            if(magChars.containsKey(i) && magChars.get(i) >=  1){
                magChars.put(i, magChars.get(i) - 1);
            }
            else{
                return false;
            }
        }
        return true;
}

For a far more efficient check the solution in Ransom Note - Easy