Задача: 767. Reorganize String
Сложность: medium

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

Пример:

Input: s = "aab"
Output: "aba"

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

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

2⃣На каждом шаге извлекаем символ с максимальным count. Если он не равен последнему добавленному в ответ — добавляем в результат.

3⃣Иначе достаём второй по приоритету символ. Добавляем его, уменьшаем count, возвращаем первый символ обратно в кучу.

😎 Решение:

import (
    "container/heap"
)

type Element struct {
    count int
    char  byte
}

type PriorityQueue []*Element

func (pq PriorityQueue) Len() int { return len(pq) }
func (pq PriorityQueue) Less(i, j int) bool { return pq[i].count > pq[j].count }
func (pq PriorityQueue) Swap(i, j int) { pq[i], pq[j] = pq[j], pq[i] }

func (pq *PriorityQueue) Push(x interface{}) { *pq = append(*pq, x.(*Element)) }
func (pq *PriorityQueue) Pop() interface{} {
    old := *pq
    n := len(old)
    x := old[n-1]
    *pq = old[0 : n-1]
    return x
}

func reorganizeString(s string) string {
    charCounts := make([]int, 26)
    for _, c := range s {
        charCounts[c-'a']++
    }

    pq := &PriorityQueue{}
    heap.Init(pq)
    for i := 0; i < 26; i++ {
        if charCounts[i] > 0 {
            heap.Push(pq, &Element{charCounts[i], byte(i + 'a')})
        }
    }

    result := []byte{}
    for pq.Len() > 0 {
        first := heap.Pop(pq).(*Element)
        if len(result) == 0 || first.char != result[len(result)-1] {
            result = append(result, first.char)
            if first.count > 1 {
                first.count--
                heap.Push(pq, first)
            }
        } else {
            if pq.Len() == 0 {
                return ""
            }
            second := heap.Pop(pq).(*Element)
            result = append(result, second.char)
            if second.count > 1 {
                second.count--
                heap.Push(pq, second)
            }
            heap.Push(pq, first)
        }
    }

    return string(result)
}

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

Задача: 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)
  }
}

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