Exercises

The following exercises provide you with the opportunity to practice with string matching and the sliding window technique. The solutions to these exercises are found in the section .

1. Implement a new version of the DivisionHasher from Chapter 10 so that it can now hash strings instead of integers. Use the approach of the initial_hash function from our final implementation of Rabin-Karp. (I warned you that this would be an exercise!)

2. Here’s a sliding window exercise for you. Write a function that accepts a string. The function should return the maximum number of vowels that are contained within any three-character substring (of the original string).

   For example, the correct answer for the string "spider" is 2 since the three-character substring "ide" contains 2 vowels. There’s no three-character substring within "spider" that contains a greater number of vowels than 2.

   On the other hand, the correct answer for the string "beautiful" is 3 since the substring "eau" contains 3 vowels.

   For the purposes of this exercise, we’ll say that vowels are the letters a, e, i, o, and u.

3. New Concept: In this chapter, when discussing the sliding window technique, we always worked with a window of a fixed size. That is, as the window slides, it always contains the same number of values. However, there’s another form of the sliding window technique in which the window doesn’t just slide, but also expands or contracts. Here’s such a problem:

   Write a function that accepts a string, and returns the length of the longest substring that doesn’t contain any duplicate characters.

   For example, in the string "ababcdabca", the longest substring that doesn’t contain any duplicate characters is "abcd", starting at index 2. It has 4 characters, so our function should return 4.

   (There’s another substring with the length of 4, namely, "bcda", which starts at index 3. In any case, though, there’s no substring that has a length greater than 4.)