Задача: 1062. Longest Repeating Substring
Сложность: medium

Дана строка s. Вернуть длину самой длинной повторяющейся подстроки. Если повторяющаяся подстрока отсутствует, вернуть 0.

Пример:

Input: s = "abcd"
Output: 0
Explanation: There is no repeating substring.

👨‍💻 Алгоритм:

1⃣Перемещайте скользящее окно длиной L по строке длиной N.

2⃣Проверьте, находится ли строка в скользящем окне в хэш-наборе уже виденных строк. Если да, то повторяющаяся подстрока находится здесь. Если нет, сохраните строку из скользящего окна в хэш-наборе.

3⃣Очевидный недостаток этого подхода — большое потребление памяти в случае длинных строк.

😎 Решение:

package main

import "strings"

func search(L, n int, S string) int {
    seen := make(map[string]bool)
    for start := 0; start <= n-L; start++ {
        tmp := S[start : start+L]
        if seen[tmp] {
            return start
        }
        seen[tmp] = true
    }
    return -1
}

func longestRepeatingSubstring(S string) int {
    n := len(S)
    left, right := 1, n
    for left <= right {
        L := left + (right-left)/2
        if search(L, n, S) != -1 {
            left = L + 1
        } else {
            right = L - 1
        }
    }
    return left - 1
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 859. Buddy Strings
Сложность: easy

Даны две строки s и goal. Верните true, если вы можете поменять местами две буквы в s так, чтобы результат был равен goal, в противном случае верните false.

Обмен буквами определяется как взятие двух индексов i и j (нумерация с 0), таких что i != j, и обмен символов в s[i] и s[j].

Например, обмен символов на индексах 0 и 2 в строке "abcd" приводит к "cbad".

Пример:

Input: s = "ab", goal = "ba"
Output: true
Explanation: You can swap s[0] = 'a' and s[1] = 'b' to get "ba", which is equal to goal.

👨‍💻 Алгоритм:

1⃣Если количество символов в строках s и goal разное, возвращаем false. Если s == goal, используем хеш-таблицу или массив из 26 элементов для хранения частоты каждого символа в строке s. Если какой-либо символ встречается более одного раза, можно поменять местами две одинаковые буквы, возвращаем true. Иначе возвращаем false.

2⃣Иначе, если s != goal, инициализируем firstIndex и secondIndex значениями -1 для хранения индексов символов в строке s, которые отличаются от символов в строке goal на тех же индексах. Итерируем по каждому индексу i в строке s: если символы s[i] и goal[i] разные, сохраняем текущий индекс. Если firstIndex == -1, обновляем firstIndex = i. Если firstIndex != -1, но secondIndex == -1, обновляем secondIndex = i. Если оба индекса уже обновлены, возвращаем false.

3⃣Если обновлен только firstIndex, возвращаем false. Иначе, все символы обеих строк одинаковы, кроме двух индексов. Поэтому s[firstIndex] должен быть равен goal[secondIndex], и s[secondIndex] должен быть равен goal[firstIndex], чтобы строки стали равны после обмена.

😎 Решение:

func buddyStrings(s string, goal string) bool {
    if len(s) != len(goal) {
        return false
    }
    if s == goal {
        freq := make(map[rune]int)
        for _, ch := range s {
            freq[ch]++
            if freq[ch] > 1 {
                return true
            }
        }
        return false
    }

    firstIndex, secondIndex := -1, -1
    for i := range s {
        if s[i] != goal[i] {
            if firstIndex == -1 {
                firstIndex = i
            } else if secondIndex == -1 {
                secondIndex = i
            } else {
                return false
            }
        }
    }

    return secondIndex != -1 &&
           s[firstIndex] == goal[secondIndex] &&
           s[secondIndex] == goal[firstIndex]
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 125. Valid Palindrome
Сложность: easy

Фраза является палиндромом, если после преобразования всех заглавных букв в строчные и удаления всех неалфавитно-цифровых символов она читается одинаково как слева направо, так и справа налево. Алфавитно-цифровые символы включают в себя буквы и цифры.

Для данной строки s верните true, если она является палиндромом, и false в противном случае.

Пример:

Input: s = "A man, a plan, a canal: Panama"
Output: true
Explanation: "amanaplanacanalpanama" is a palindrome.

👨‍💻 Алгоритм:

1⃣Поскольку входная строка содержит символы, которые нам нужно игнорировать при проверке на палиндром, становится трудно определить реальную середину нашего палиндромического ввода.

2⃣Вместо того, чтобы двигаться от середины наружу, мы можем двигаться внутрь к середине! Если начать перемещаться внутрь, с обоих концов входной строки, мы можем ожидать увидеть те же символы в том же порядке.

3⃣Результирующий алгоритм прост:
1. Установите два указателя, один на каждом конце входной строки.
2. Если ввод является палиндромом, оба указателя должны указывать на эквивалентные символы в любой момент времени.
3. Если это условие не выполняется в какой-либо момент времени, мы прерываемся и возвращаемся раньше.
4. Мы можем просто игнорировать неалфавитно-цифровые символы, продолжая двигаться дальше.
5. Продолжайте перемещение внутрь, пока указатели не встретятся в середине.

😎 Решение:

func isPalindrome(s string) bool {
    i := 0
    j := len(s) - 1
    for i < j {
        for i < j && !isalnum(s[i]) {
            i++
        }
        for i < j && !isalnum(s[j]) {
            j--
        }
        if tolower(s[i]) != tolower(s[j]) {
            return false
        }
        i++
        j--
    }
    return true
}

func isalnum(c byte) bool {
    return ('0' <= c && c <= '9') || ('a' <= c && c <= 'z') ||
        ('A' <= c && c <= 'Z')
}

func tolower(c byte) byte {
    if 'A' <= c && c <= 'Z' {
        return c - 'A' + 'a'
    }
    return c
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 819. Most Common Word
Сложность: easy

Дана строка paragraph и массив строк banned, представляющий запрещенные слова. Верните наиболее часто встречающееся слово, которое не запрещено. Гарантируется, что существует хотя бы одно слово, которое не запрещено, и что ответ является уникальным.

Слова в paragraph нечувствительны к регистру, и ответ должен быть возвращен в нижнем регистре.

Пример:

Input: paragraph = "Bob hit a ball, the hit BALL flew far after it was hit.", banned = ["hit"]
Output: "ball"
Explanation: 
"hit" occurs 3 times, but it is a banned word.
"ball" occurs twice (and no other word does), so it is the most frequent non-banned word in the paragraph. 
Note that words in the paragraph are not case sensitive,
that punctuation is ignored (even if adjacent to words, such as "ball,"), 
and that "hit" isn't the answer even though it occurs more because it is banned.

👨‍💻 Алгоритм:

1⃣Заменяем всю пунктуацию пробелами и одновременно переводим каждую букву в нижний регистр. Это можно сделать и в два этапа, но здесь мы объединяем их в один этап.

2⃣Разбиваем полученный результат на слова, используя пробелы в качестве разделителей.

3⃣Затем итерируемся по словам, чтобы подсчитать количество появлений каждого уникального слова, исключая слова из списка запрещенных. С помощью хеш-таблицы {слово->количество} проходим по всем элементам, чтобы найти слово с наивысшей частотой.

😎 Решение:

func mostCommonWord(paragraph string, banned []string) string {
    normalizedStr := strings.Map(func(r rune) rune {
        if unicode.IsLetter(r) || unicode.IsDigit(r) {
            return unicode.ToLower(r)
        }
        return ' '
    }, paragraph)

    words := strings.Fields(normalizedStr)
    wordCount := make(map[string]int)
    bannedWords := make(map[string]bool)

    for _, word := range banned {
        bannedWords[word] = true
    }

    for _, word := range words {
        if !bannedWords[word] {
            wordCount[word]++
        }
    }

    maxWord := ""
    maxCount := 0
    for word, count := range wordCount {
        if count > maxCount {
            maxWord = word
            maxCount = count
        }
    }

    return maxWord
}

Ставь 👍 и забирай 📚 Базу знаний