Определяем уникальные символы в строке.

С примерами на Go.

Метод грубой силы (Brute force):

Выполняем 2 цикла с переменными i и j. Сравниваем str[i] и str[j]. Если они становятся равными в какой-либо точке, возвращаем false.

Для символов, которые в UTF-8 представляются одним байтом.

func hasUniqueCharacters1(str string) (string, bool) {
	for i := 0; i < len(str); i++ {
		for j := i + 1; j < len(str); j++ {
			if str[i] == str[j] {
				return str, false
			}
		}
	}
	return str, true
}

Для поддержки юникода, необходимо преобразовать строку в []rune

func hasUniqueCharacters2(str string) (string, bool) {
	chars := []rune(str)
	length := len(chars)
	for i := 0; i < length; i++ {
		for j := i + 1; j < length; j++ {
			if chars[j] == chars[i] {
				return str, false
			}
		}
	}
	return str, true
}

Сортировка значений

Чтобы не реализовывать методы интерфейса sort.Interface можно воспользоваться готовым пакетом sortutil.

func hasUniqueCharacters3(str string) (string, bool) {
	chars := sortutil.RuneSlice(str)
	length := len(chars)
	sort.Sort(chars)

	for i := 0; i < length-1; i++ {
		if chars[i] == chars[i+1] {
			return str, false
		}
		continue
	}
	return str, true
}

Вариант сортировки без реализации методов интерфейса.

func hasUniqueCharacters4(str string) (string, bool) {
	chars := []rune(str)
	length := len(chars)
	sort.Slice(chars, func(i int, j int) bool {
		return chars[i] < chars[j]
	})
	for i := 0; i < length-1; i++ {
		if chars[i] == chars[i+1] {
			return str, false
		}
		continue
	}
	return str, true
}

Использование дополнительной структуры данных

Использование big.Int, для хранения набора битов:

func hasUniqueCharacters5(str string) (string, bool) {
	var bits big.Int
	for _, char := range str {
		val := int(char)
		if bits.Bit(val) != 0 {
			return str, false
		}
		bits.SetBit(&bits, val, 1)
	}
	return str, true
}

Использование map с булевыми значениями

func hasUniqueCharacters6(str string) (string, bool) {
	var bits = make(map[int]bool, len(str))
	for _, char := range str {
		val := int(char)
		if bits[val] {
			return str, false
		}
		bits[val] = true
	}
	return str, true
}

Если нужны только значения ASCII (8 бит).

Понадобится слайс с логическими значениями заданной длины - 256. По умолчанию все элементы слайса будут равны false.

const MAX_CHAR = 256

func hasUniqueCharacters7(str string) (string, bool) {
	// если размер больше 256,
	// то какие-либо символы должны были повториться
	if len(str) > MAX_CHAR {
		return str, false
	}

	chars := make([]bool, MAX_CHAR)
	for _, char := range str {
		val := int(char)
		if chars[val] {
			return str, false
		}
		chars[val] = true
	}
	return str, true
}

Использование побитовых операторов

Подходит для символов в диапазоне a-z в таблице ASCII.

Вместо использования массивов, возьмём целочисленное значение int.

Каждый бит в целочисленном значении можно рассматривать как флаг, поэтому в конечном итоге int представляет собой массив бит (флаг).

int имеет фиксированный размер, обычно 4 байта, что означает 8 * 4 = 32 бита (флаги).

Когда мы перебираем строку, мы находим значение int символа по отношению к 'a'.

Затем бит в этом значении int устанавливается в 1 с помощью побитового сдвига влево 1 << val .

Далее проверяем установлен ли уже бит в этом значении, с помощью оператора AND &. Возвращаем false.

Битовая маска. 10111011 & 00001000 = 00001000

Если бит не установлен в заданном месте, то обновляем значение checker, с помощью оператора OR |

Merging. 00000001 | 00001000 = 00001001

func hasUniqueCharacters8(str string) (string, bool) {
	checker := 0
	for _, char := range str {
		index := char - 'a'
		val := 1 << index
		if checker & val > 0 {
			return str, false
		}
		checker |= val
	}
	return str, true
}

Тесты

В тестах, в аргументы функции передаётся строка abcdefghijklmnopqrstuvwxyz.

go test -bench BenchmarkCountLetters -benchtime=10000000x -benchmem

goos: windows
goarch: amd64
pkg: benching
cpu: Intel(R) Core(TM) i5-10210U CPU @ 1.60GHz
BenchmarkCountLetters/Test_1-8          10000000               174.0 ns/op             0 B/op          0 allocs/op
BenchmarkCountLetters/Test_2-8          10000000               310.7 ns/op             0 B/op          0 allocs/op
BenchmarkCountLetters/Test_3-8          10000000               619.9 ns/op           136 B/op          2 allocs/op
BenchmarkCountLetters/Test_4-8          10000000               756.2 ns/op           168 B/op          3 allocs/op
BenchmarkCountLetters/Test_5-8          10000000               400.2 ns/op            48 B/op          1 allocs/op
BenchmarkCountLetters/Test_6-8          10000000              1653 ns/op             459 B/op          3 allocs/op
BenchmarkCountLetters/Test_7-8          10000000                37.31 ns/op            0 B/op          0 allocs/op
BenchmarkCountLetters/Test_8-8          10000000                55.49 ns/op            0 B/op          0 allocs/op

Код и тесты производительности можно найти на гитхабе