Перестановка в строке

Постановка задачи

s1 = "ab", s2 = "eidbaooo"

true

s1 = "ab", s2 = "eidboaoo"

false

Решение

Перестановка не зависит от порядка символов. Для строк "ab" и "ba" набор частот одинаковый: одна буква a и одна буква b. Значит, нам не нужно сравнивать подстроки как строки. Достаточно сравнить частоты символов.

Наивное решение перебирает все подстроки длины s1.length внутри s2, для каждой заново считает частоты и сравнивает их с частотами s1. Это очень неэффективно и нужно найти другое решение.

Длина подстроки s1 фиксирована. При поиске перестановки внутри s2 соседние подстроки в позициях i и i+1 отличаются только одним вышедшим символом слева и одним новым символом справа. Это позволяет применить фиксированное скользящее окно.

Идея решения:

Размер окна фиксирован и равен len(s1). Мы заранее считаем частоты символов в s1, затем двигаем окно такой же длины по s2.

При каждом сдвиге:

1. добавляем новый символ справа;
2. убираем старый символ слева;
3. сравниваем частоты окна с частотами s1.

Так как в строках только строчные английские буквы, для хранения и подсчета частот можно использовать массив из 26 чисел. Индекс символа c равен c - 'a'.

Основные шаги:

1. Если s1 длиннее s2, сразу возвращаем false.
2. Создаем два массива частот длины 26: targetCount и windowCount.
3. Заполняем частоты для s1 и первого окна в s2.
4. Если частоты равны, возвращаем true.
5. Сдвигаем окно по s2:
   • добавляем новый правый символ;
   • удаляем символ, который вышел слева;
   • проверяем равенство частот.
6. Если подходящее окно не найдено, возвращаем false.

Рассмотрим пример:

s1 = "ab", s2 = "eidbaooo"

Ищем окно длины 2.

1. "ei" - частоты не совпадают.

2. "id" - частоты не совпадают.

3. "db" - частоты не совпадают.

4. "ba" - частоты совпадают.

Окно "ba" содержит те же символы, что и "ab", поэтому ответ true.

Оценка сложности

Временная сложность

Мы строим первое окно и затем один раз проходим по строке s2. На каждом шаге сравниваем массивы длины 26.

Итоговая временная сложность: O(n), где n - длина s2.

Пространственная сложность

Мы используем два массива по 26 элементов. Размер этих массивов не зависит от длины входных строк.

Пространственная сложность: O(1).

Код решения

Приведем код решения.

func checkInclusion(s1 string, s2 string) bool {
    if len(s1) > len(s2) {
        return false
    }
 
    var targetCount [26]int
    var windowCount [26]int
    for i := 0; i < len(s1); i++ {
        targetCount[s1[i]-'a']++
        windowCount[s2[i]-'a']++
    }
 
    if targetCount == windowCount {
        return true
    }
 
    for right := len(s1); right < len(s2); right++ {
        windowCount[s2[right]-'a']++
        windowCount[s2[right-len(s1)]-'a']--
 
        if targetCount == windowCount {
            return true
        }
    }
 
    return false
}

Итоги

Задача Permutation in String показывает, как фиксированное окно помогает искать подстроку по составу символов, а не по точному порядку.

1. Суть алгоритма: считаем частоты символов в s1 и сравниваем их с частотами каждого окна длины s1.length в строке s2.
2. Эффективность:
   • Временная сложность: O(n), так как окно сдвигается по s2 один раз, а сравнение частот занимает константное время.
   • Пространственная сложность: O(1), потому что массивы частот имеют фиксированный размер 26.
3. Граничные случаи:
   • s1 длиннее s2: перестановка не может быть подстрокой.
   • Первое окно уже подходит: возвращаем true без дальнейших сдвигов.
4. Оптимальное решение: мы не генерируем перестановки и не сортируем каждую подстроку, а поддерживаем частоты окна инкрементально.