Задача: 424. Longest Repeating Character Replacement
Сложность: medium

Вам дана строка s и целое число k. Вы можете выбрать любой символ строки и заменить его на любой другой заглавный английский символ. Вы можете выполнить эту операцию не более k раз.

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

Пример:
Input: s = "ABAB", k = 2
Output: 4
Explanation: Replace the two 'A's with two 'B's or vice versa.

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

1⃣Определите диапазон поиска. Минимальная длина подстроки с одинаковыми символами всегда равна 1 (назовем ее min), а максимальная длина подстроки может быть равна длине данной строки (назовем ее max). Ответ будет лежать в диапазоне [min, max] (включительно).

2⃣Инициализируйте две переменные lo и hi для бинарного поиска. lo всегда указывает на длину допустимой строки, а hi - на недопустимую длину. Изначально lo равно 1, а hi равно max+1.

3⃣Выполните бинарный поиск, чтобы найти максимальное значение lo, которое представляет самую длинную допустимую подстроку. В конце lo будет содержать ответ, а hi будет на единицу больше lo.

😎 Решение:

package main

func characterReplacement(s string, k int) int {
    lo, hi := 1, len(s)+1

    for lo + 1 < hi {
        mid := lo + (hi - lo) / 2
        if canMakeValidSubstring(s, mid, k) {
            lo = mid
        } else {
            hi = mid
        }
    }
    return lo
}

func canMakeValidSubstring(s string, substringLength, k int) bool {
    freqMap := make([]int, 26)
    maxFrequency := 0
    start := 0

    for end := 0; end < len(s); end++ {
        freqMap[s[end] - 'A']++

        if end + 1 - start > substringLength {
            freqMap[s[start] - 'A']--
            start++
        }

        if freqMap[s[end] - 'A'] > maxFrequency {
            maxFrequency = freqMap[s[end] - 'A']
        }
        if substringLength - maxFrequency <= k {
            return true
        }
    }
    return false
}

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

Задача: 140. Word Break II
Сложность: hard

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

Обратите внимание, что одно и то же слово из словаря может использоваться несколько раз при разделении.

Пример:

Input: s = "catsanddog", wordDict = ["cat","cats","and","sand","dog"]
Output: ["cats and dog","cat sand dog"]

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

1⃣Инициализация и начальный вызов:
Преобразуйте массив wordDict в множество wordSet для эффективного поиска.
Инициализируйте пустой массив results для хранения допустимых предложений.
Инициализируйте пустую строку currentSentence для отслеживания конструируемого предложения.
Вызовите функцию backtrack с исходной строкой s, множеством wordSet, текущим предложением currentSentence, массивом результатов results и начальным индексом, установленным в 0 — начало входной строки.
Верните results после завершения работы backtrack.

2⃣Функция backtrack:
Базовый случай: Если startIndex равен длине строки, добавьте currentSentence в results и вернитесь, так как это означает, что currentSentence представляет собой допустимое предложение.
Итерация по возможным значениям endIndex от startIndex + 1 до конца строки.

3⃣Обработка и рекурсия:
Извлеките подстроку word от startIndex до endIndex - 1.
Если word найдено в wordSet:
Сохраните текущее значение currentSentence в originalSentence.
Добавьте word к currentSentence (с пробелом, если это необходимо).
Рекурсивно вызовите backtrack с обновленным currentSentence и endIndex.
Сбросьте currentSentence к его исходному значению (originalSentence) для отката и попробуйте следующий endIndex.
Вернитесь из функции backtrack.

😎 Решение:

package main

import (
  "strings"
)

func wordBreak(s string, wordDict []string) []string {
  wordSet := make(map[string]struct{})
  for _, word := range wordDict {
    wordSet[word] = struct{}{}
  }
  var results []string
  backtrack(s, wordSet, "", &results, 0)
  return results
}

func backtrack(s string, wordSet map[string]struct{}, currentSentence string, results *[]string, startIndex int) {
  if startIndex == len(s) {
    *results = append(*results, currentSentence)
    return
  }

  for endIndex := startIndex + 1; endIndex <= len(s); endIndex++ {
    word := s[startIndex:endIndex]
    if _, exists := wordSet[word]; exists {
      originalSentence := currentSentence
      if len(currentSentence) > 0 {
        currentSentence += " "
      }
      currentSentence += word
      backtrack(s, wordSet, currentSentence, results, endIndex)
      currentSentence = originalSentence
    }
  }
}

func main() {
  s := "leetcode"
  wordDict := []string{"leet", "code"}
  results := wordBreak(s, wordDict)
  for _, result := range results {
    println(result)
  }
}

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

Задача: 1663. Smallest String With A Given Numeric Value
Сложность: medium

Числовое значение строчной буквы определяется ее позицией (начиная с 1) в алфавите, поэтому числовое значение a равно 1, числовое значение b равно 2, числовое значение c равно 3 и так далее.

Числовое значение строки, состоящей из строчных букв, определяется как сумма числовых значений ее символов. Например, числовое значение строки "abe" равно 1 + 2 + 5 = 8.

Вам даны два целых числа n и k. Верните лексикографически наименьшую строку длиной n с числовым значением, равным k.

Обратите внимание, что строка x лексикографически меньше строки y, если x идет перед y в словарном порядке, то есть либо x является префиксом y, либо, если i - первая позиция, где x[i] != y[i], то x[i] идет перед y[i] в алфавитном порядке.

Пример:

Input: n = 3, k = 27
Output: "aay"
Explanation: The numeric value of the string is 1 + 1 + 25 = 27, and it is the smallest string with such a value and length equal to 3.

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

1⃣Построить строку или массив символов result для хранения выбранных символов для каждой позиции.

2⃣Итерация от позиции 1 до n и заполнение символом каждой позиции:
Найти позиции, которые нужно заполнить, исключая текущую позицию, задаваемую переменной positionsLeft как n - position - 1.
Если значение k больше, чем positionsLeft * 26, зарезервировать числовое значение 26 (символ z) для всех оставшихся позиций positionsLeft. Вычислить значение текущей позиции, заданное переменной add, как k - (positionsLeft * 26). Вычесть рассчитанное значение add из k, чтобы найти оставшееся значение k после заполнения текущей позиции.
Иначе, заполнить текущую позицию символом a, имеющим числовое значение 1. Вычесть 1 из k, чтобы найти оставшееся значение k после заполнения текущей позиции.

3⃣Повторять процесс, пока все позиции не будут заполнены.

😎 Решение:

func getSmallestString(n int, k int) string {
    result := make([]byte, n)
    for i := 0; i < n; i++ {
        result[i] = 'a'
    }
    
    for position := 0; position < n; position++ {
        positionsLeft := (n - position - 1)
        if k > positionsLeft * 26 {
            add := k - (positionsLeft * 26)
            result[position] = byte('a' + add - 1)
            k -= add
        } else {
            k -= 1
        }
    }
    
    return string(result)
}

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

Задача: 1061. Lexicographically Smallest Equivalent String
Сложность: medium

Даны две строки одинаковой длины s1 и s2, а также строка baseStr.

Мы говорим, что символы s1[i] и s2[i] эквивалентны.

Например, если s1 = "abc" и s2 = "cde", то 'a' == 'c', 'b' == 'd' и 'c' == 'e'. Эквивалентные символы следуют правилам рефлексивности, симметрии и транзитивности.

Верните лексикографически наименьшую эквивалентную строку baseStr, используя информацию об эквивалентности из s1 и s2.

Пример:

Input: s1 = "parker", s2 = "morris", baseStr = "parser"
Output: "makkek"
Explanation: Based on the equivalency information in s1 and s2, we can group their characters as [m,p], [a,o], [k,r,s], [e,i].
The characters in each group are equivalent and sorted in lexicographical order.
So the answer is "makkek".

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

1⃣Создайте матрицу смежности adjMatrix размером 26x26 для хранения рёбер и массив visited для отслеживания посещённых символов.

2⃣Итеративно обрабатывайте каждый символ от 0 до 25:

Если символ ещё не посещён, выполните DFS, начиная с этого символа, и сохраните все пройденные символы в векторе component, а минимальный из этих символов в переменной minChar.
Обновите все символы из component до minChar в векторе mappingChar, который хранит окончательное сопоставление символов baseStr.

3⃣Пройдите по baseStr и создайте итоговую строку ans, используя символы из mappingChar.

😎 Решение:

package main

func DFS(src int, adjMatrix *[26][26]int, visited *[26]int, component *[]int, minChar *int) {
    visited[src] = 1
    *component = append(*component, src)
    if src < *minChar {
        *minChar = src
    }
    for i := 0; i < 26; i++ {
        if adjMatrix[src][i] != 0 && visited[i] == 0 {
            DFS(i, adjMatrix, visited, component, minChar)
        }
    }
}

func smallestEquivalentString(s1 string, s2 string, baseStr string) string {
    var adjMatrix [26][26]int
    for i := 0; i < len(s1); i++ {
        adjMatrix[s1[i]-'a'][s2[i]-'a'] = 1
        adjMatrix[s2[i]-'a'][s1[i]-'a'] = 1
    }
    mappingChar := [26]int{}
    for i := 0; i < 26; i++ {
        mappingChar[i] = i
    }
    visited := [26]int{}
    for c := 0; c < 26; c++ {
        if visited[c] == 0 {
            component := []int{}
            minChar := 27
            DFS(c, &adjMatrix, &visited, &component, &minChar)
            for _, vertex := range component {
                mappingChar[vertex] = minChar
            }
        }
    }
    ans := make([]byte, len(baseStr))
    for i := range baseStr {
        ans[i] = byte(mappingChar[baseStr[i]-'a'] + 'a')
    }
    return string(ans)
}

func main() {
    // Example usage
    s1 := "leetcode"
    s2 := "programs"
    baseStr := "sourcecode"
    result := smallestEquivalentString(s1, s2, baseStr)
    println(result)
}

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

Задача: 912. Sort an Array
Сложность: medium

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

Пример:

Input: nums = [5,2,3,1]
Output: [1,2,3,5]

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

1⃣Используем алгоритм "Сортировка слиянием" (Merge Sort), который обеспечивает время выполнения O(n log n) и минимально возможную пространственную сложность для стабильного сортировочного алгоритма.

2⃣Разделить массив на две половины.
Рекурсивно отсортировать каждую половину.

3⃣Слить две отсортированные половины.

😎 Решение:

package main

import (
    "fmt"
)

func mergeSort(nums []int) {
    if len(nums) > 1 {
        mid := len(nums) / 2
        left_half := make([]int, mid)
        right_half := make([]int, len(nums)-mid)

        copy(left_half, nums[:mid])
        copy(right_half, nums[mid:])

        mergeSort(left_half)
        mergeSort(right_half)

        i, j, k := 0, 0, 0
        for i < len(left_half) && j < len(right_half) {
            if left_half[i] < right_half[j] {
                nums[k] = left_half[i]
                i++
            } else {
                nums[k] = right_half[j]
                j++
            }
            k++
        }

        for i < len(left_half) {
            nums[k] = left_half[i]
            i++
            k++
        }

        for j < len(right_half) {
            nums[k] = right_half[j]
            j++
            k++
        }
    }
}

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

Задача: 811. Subdomain Visit Count
Сложность: medium

Веб-сайт с доменом "discuss.leetcode.com" состоит из различных поддоменов. На верхнем уровне у нас есть "com", на следующем уровне - "leetcode.com", и на самом нижнем уровне - "discuss.leetcode.com". Когда мы посещаем домен, такой как "discuss.leetcode.com", мы также автоматически посещаем родительские домены "leetcode.com" и "com".

Домен с парным счетчиком - это домен, который имеет один из двух форматов "rep d1.d2.d3" или "rep d1.d2", где rep - это количество посещений домена, а d1.d2.d3 - это сам домен.

Например, "9001 discuss.leetcode.com" - это домен с парным счетчиком, указывающий на то, что discuss.leetcode.com был посещен 9001 раз.
Дан массив доменов с парными счетчиками cpdomains, верните массив доменов с парными счетчиками для каждого поддомена во входных данных. Вы можете вернуть ответ в любом порядке.

Пример:

Input: cpdomains = ["9001 discuss.leetcode.com"]
Output: ["9001 leetcode.com","9001 discuss.leetcode.com","9001 com"]
Explanation: We only have one website domain: "discuss.leetcode.com".
As discussed above, the subdomain "leetcode.com" and "com" will also be visited. So they will all be visited 9001 times.

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

1⃣Следуем указаниям из условия задачи.

2⃣Для адреса вида a.b.c, подсчитываем a.b.c, b.c и c. Для адреса вида x.y, подсчитываем x.y и y.

3⃣Для подсчета этих строк используем хеш-таблицу. Для разделения строк на требуемые части используем библиотечные функции split.

😎 Решение:

package main

import (
    "strconv"
    "strings"
)

func subdomainVisits(cpdomains []string) []string {
    ans := make(map[string]int)
    for _, domain := range cpdomains {
        parts := strings.Split(domain, " ")
        count, _ := strconv.Atoi(parts[0])
        frags := strings.Split(parts[1], ".")
        for i := range frags {
            subdomain := strings.Join(frags[i:], ".")
            ans[subdomain] += count
        }
    }
    res := make([]string, 0, len(ans))
    for dom, ct := range ans {
        res = append(res, strconv.Itoa(ct)+" "+dom)
    }
    return res
}

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

🔥 Записал видос "Как за 3 минуты настроить Автоотклики на вакансии HeadHunter" больше не придется заниматься этой унылой рутиной

📺 Видео: https://youtu.be/G_FOwEGPwlw