11: - A Common-Sense Guide to Data Structures and Algorithms in Python, Volume 2 (for True Epub) - Jay Wengrow - RutLib.com

Chapter 11

These are the solutions to the .

Here, I’ve updated the DivisionHasher class to incorporate the Rabin-Karp initial hash function as a basic way to hash any string:

	import random


	class DivisionHasher:

	def __init__(self, array_length):
	self.array_length = array_length
	self.base = 26

	# Choose a random prime number:
	p = random.randint(1000, 10000)
	while not self.is_prime(p):
	p = random.randint(1000, 10000)

	self.prime = p

	def hash(self, key):
	key = str(key)

	result = self.character_hash_code(key[0]) % self.prime

	for i in range(1, len(key)):
	result = \
	(result * self.base + self.character_hash_code(key[i])) \
	% self.prime

	return result

	def character_hash_code(self, char):
	return ord(char) - 97

	# Fermat's Primality Test
	def is_prime(self, number):
	for _ in range(100):
	a = random.randint(1, number - 1)
	if pow(a, number - 1, number) != 1:
	return False

	return True

Note that in the hash function, I first convert the key to a string just in case it comes in as something else, such as an integer.

In the following code, I use the sliding window technique by maintaining a window of three characters at all times:

	def max_vowels(string):
	num_of_window_vowels = 0

	for i in range(3):
	if is_vowel(string[i]):
	num_of_window_vowels += 1

	max_num_of_vowels_so_far = 0

	for i in range(3, len(string)):
	if is_vowel(string[i - 3]):
	num_of_window_vowels -= 1
	if is_vowel(string[i]):
	num_of_window_vowels += 1

	max_num_of_vowels_so_far = \
	max(max_num_of_vowels_so_far, num_of_window_vowels)

	return max_num_of_vowels_so_far


	def is_vowel(char):
	return char in {'a': True, 'e': True, 'i': True, 'o': True, 'u': True}

I begin by creating the initial window and counting how many vowels it contains. We store this number inside the variable num_of_window_vowels. Then, we move the sliding window along using a for loop that runs from index 3 until the end of the string. Each time we shift the window forward, we check to see if we dropped a vowel, in which case we decrement the num_of_window_vowels by 1. We also check to see if the window gained a vowel on its right end, in which case we increment num_of_window_vowels by 1.

We track the greatest number of vowels in any window within the max_num_of_vowels_so_far variable, which is what we return at the end of the function.

First, I’ll show you the code, and then I’ll explain it:

	def length_of_longest_substring(string):
	if not string:
	return 0

	left = 0
	right = 0
	max_distance_so_far = 0
	current_window_chars = {}

	while right < len(string):
	if string[right] not in current_window_chars:
	current_window_chars[string[right]] = True
	max_distance_so_far = max(max_distance_so_far, right - left)
	right += 1
	else:
	del current_window_chars[string[left]]
	left += 1

	return max_distance_so_far + 1

This code features a sliding window, but the size of the window expands and contracts as needed. To allow our window to change size, we establish two pointers, with left pointing to the left-most index of the window, and right pointing to the right-most index of the window.

Let me walk through what the code does using an example.

Say that our input string is "abac". The left and right pointers start out both pointing to the first character, "a". Throughout our algorithm, we keep track of the max_distance_so_far, which is the greatest distance between the two pointers. At the beginning, since both pointers are at the same spot, their distance is 0.

We also establish a hash table called current_window_chars, which keeps track of which characters are contained within the current window. If a character is inside the window, the hash table will contain that character as a key. (I made True the arbitrary value associated with each key.)

The guts of the algorithm is a while loop that lasts until the right pointer reaches the end of the string. In this loop, we move the right pointer to the right, one character at a time. As we do, we expand the window, since the left pointer is standing still. With each new character that enters our window, we insert that character into the current_window_chars hash table.

After one round of the loop with our example string "abac", left points to the first "a" and right points to the "b". The distance between the two pointers is 1, and given that this is the maximum distance we’ve encountered so far, this becomes the new max_distance_so_far.

In each round of the loop, we check the hash table to ensure that the new character we include in the window isn’t already inside the hash table.

In the next round of the loop, the right pointer encounters the second "a". This is an “invalid” window since it contains two instances of the character "a". That is, right points to the second "a" while left still points to the first "a".

Now, we might be tempted to have the left pointer skip to where the right pointer currently is and continue with the loop. However, this would be a mistake since in truth, the "b" is part of the longest valid window, "bac". So instead, we move the left pointer along, which thereby shrinks the window since now left has moved closer to right. Because the window shrinks, we also delete the old character left was pointing to from our hash table. From this point, we continue once again to move the right pointer along and expand the window once again.

In our example, the window will eventually encompass the characters "bac".

The loop finally terminates once right hits the end of the input string. At this point, max_distance_so_far will be the greatest distance between the two pointers we’ve ever encountered. In truth, though, the length of the largest window is the greatest distance plus 1. That is, in "bac", with left pointing to "b" and right pointing to "c", the distance between the two pointers is 2. However, the actual length of the substring is 3, so that’s the number our function finally returns.