Буду решать задачи из книги Г. Лакмана Макдауэлла "Карьера программиста" на языке Go.
Итак, первая, интересная, на мой взгляд, задача из раздела 1 "Массивы и строки".

1.1. Реализуйте алгоритм, определяющий, все ли символы в строке встречаются только один раз. А если при этом запрещено использование дополнительных структур данных?

1 способ: итеративный метод. Перебираем все символы в строке сравнивая их последовательно друг с другом. При нахождении первого совпадения завершаем поиск. Временная сложность O(n^2), пространственная сложность O(1)

2 способ. Если можно изменять строку, то возможно отсортировать строку и итеративным способом сравнивать сосесние символы. Временная сложность сортировки O(nlogn). Как правило сортировка очень затратная операция.

3 способ заключается в использовании структуры данных, такой как хэш-таблица, которая будет хранить логическое значение, где флаг с ASCII-кодом символа, означает, содержится ли символ алфавита i в строке. Временная сложность O(n), пространственная сложность O(n)

4 способ заключается в использовании бит-вектора.

В книге Донованa А. и Кернигана Б. Язык программирования Go рассмотрен пример битового вектора. Данная структура хорошо подходит для множества небольших положительных чисел над которым часто проводят операции объединения, пересечения, разность и д.р.

Так как у нас строка, будем использовать ASCII-коды символов.

В следующем коде мы предполагаем, что в строке есть только символы в нижнем регистре a-z. Это позволит нам использовать просто одно значение типа int.

Временная сложность будет O(n), пространственная - O(1)

func BitVector(str string) bool {
	// Тип вектора имеет одно поле. Срез беззнаковых целочисленных значений, каждый бит которых представляет возможный элемент множества
	type IntSet struct {
		words []uint
	}
	var s IntSet

	// Вычисляем размер машинного слова sizeWorld
	// На 32 разрядных платформах sizeWord будет равен 32, на 64 соответственно 64.
	const sizeWord = 32 << (^uint(0) >> 63)

	for i := 0; i < len(str); i++ {
		var charCode = str[i]

		byteIndex, indexInByte := uint(charCode/sizeWord), uint(charCode%sizeWord)
		for byteIndex >= uint(len(s.words)) {
			s.words = append(s.words, 0)
		}

		// Хотим узнать включен ли indexInByte-й бит. Проверим принадлежность множеству s.words[byteIndex]
		var bit = s.words[byteIndex] & (1 << indexInByte)
		if bit > 0 {  // != 0 значит символ с ASCII кодом charCode входит в множество
			return false
		} else {
			// Нужно найти элемент с индексом 1 и выставить ему indexInByte-й бит
			// Операцией ИЛИ выставляем indexInByte-й бит (т.е. включаем нужные биты по маске 1 << indexInByte)
			s.words[byteIndex] |= 1 << indexInByte
		}
	}

	return true
}

Все способы решения данной задачи на языке Go на GitHub

Все задачи из данной книги