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…