longest_substr_no_repeats

dz / leetcode / longest_substr_no_repeats

Summary

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

Node Tree

• URL
• cpp_implementation
  • no_inner_loop
  • hashmap_stores_last_known_position
    • repeat_pos_latest_repeating_character
      • distance_between_latest_repeating
        • postion_always_updated_at_end
• intuition
  • brute_force
• maxlen_init_negative_one

Nodes

URL
content	URL
hyperlink	https://leetcode.com/problems/longest-substring-without-repeating-characters

intuition
content	I think I can imagine a brute-force way to do this, but I vaguely remember reading about a more elegant solution The Algorithm Design Manual. Brute force involves starting at each character, and sweeping until it finds itself again, yielding approximately an O(n^2) algorithm. I think the more elegant solution involved a data structure or divide-and-conquer somehow.
children	brute_force

brute_force
content	Brute Force involves two loops. The outer loop sweeps through every character. The inner loop starts at that character position, and continues until it finds a match or reaches the end. At the end of the inner loop, you'll have a size. If the size is the greatest one seen so far, it is stored along with the indice.
parents	intuition

cpp_implementation
content	So the CPP implementation is kinda weird. It's using a hash map to keep track of character positions. It's hard to tell if this is correct or not. It just seems overly complicated. There is an alternative verson that uses a flat array instead.
children	no_inner_loop, hashmap_stores_last_known_position

no_inner_loop
content	Ah, I'm starting to see a pattern with these solutions, they do not have an inner loop.
parents	cpp_implementation

maxlen_init_negative_one
content	The maxlen value is initialized at -1. That way, the first character (index 0) has a maxlen of 1. Not an obvious first thing.

hashmap_stores_last_known_position
content	The hashmap data structure here is used to store the last known location of a particular character, if it existed at all. All that matters is the last seen character. The previous ones can be discarded.
children	repeat_pos_latest_repeating_character
parents	cpp_implementation

repeat_pos_latest_repeating_character
content	The repeat position stored the latest repeating character (the greatest indice).
children	distance_between_latest_repeating
parents	hashmap_stores_last_known_position

distance_between_latest_repeating
content	The distance is measured between the latest (last) repeating character, and the position of the current character. This is stored away if it is the longest distance it has seen.
children	postion_always_updated_at_end
parents	repeat_pos_latest_repeating_character

postion_always_updated_at_end
content	The character position is always stored away at the end.
parents	distance_between_latest_repeating