Create a function. Takes in a string. Returns true if there are duplicate characters in the string otherwise returns false.

Solution

Create a hash set (hash table), where each key is a character in the string. Loop over the string and add characters to the hash set if they are not already in it. If a character is already in the hash set, return true. Return false if the loop completes without finding a duplicate.

NOTE: Hash table lookups are O(1).

Follow-Up

What happens if the string is infinitely long?

The string cannot be infinitely long, since, assuming a UTF-16 character set, once all the characters in the set are exhausted, you must begin to duplicate characters. This must occur at n+1, where n is the size of the character set.

package main

// findDuplicate returns true if `s` has a duplicate. Otherwise, returns false.
func findDuplicate(s string) bool {
	table := make(map[rune]bool)
	// Loop over `s`. If a character (rune) is in hash set, return true. If not,
	// add the character to the hash set.
	for _, elem := range s {
		_, ok := table[elem]
		if ok {
			return true
		} else {
			table[elem] = true
		}
	}
	return false
}