План курса / Все задачи / Алгоритмы и структуры данных

Поиск анаграмм

средне

# решено

Даны строки s и t. Нужно найти все индексы в строке s, с которых начинается подстрока — анаграмма строки t, и вернуть их в порядке возрастания. Считается, что символы могут быть любыми и заранее не известны (алфавит не ограничен), но на практике строки будут состоять только из символов ascii.

Пример 1:

Ввод: s = "abacbaab", t = "aab"  
Вывод: [0,4,5]

Пример 2:

Ввод: s = "baba", t = "ab"
Вывод: [0,1,2]

Ограничения:

len(s) >= 1
len(t) >= 1
s и t содержат только ascii символы

public class Solution {
    public static List<int> FindAnagrams(string s, string t) {
        List<int> res = new List<int>();
        if (t.Length > s.Length) {
            return res;
        }

        // diff[c] > 0 — символ нужен, diff[c] < 0 — символ лишний
        Dictionary<char, int> diff = new Dictionary<char, int>();
        foreach (char ch in t) {
            if (diff.ContainsKey(ch)) {
                diff[ch]++;
            } else {
                diff[ch] = 1;
            }
        }

        int l = 0;
        int r = 0;

        // Заполняем начальное окно длины len(t)
        while (r < t.Length) {
            char current = s[r];
            if (diff.ContainsKey(current)) {
                diff[current]--;
                if (diff[current] == 0) {
                    diff.Remove(current);
                }
            } else {
                diff[current] = -1;
            }
            r++;
        }

        if (diff.Count == 0) {
            res.Add(0);
        }

        // Двигаем окно по строке s
        while (r < s.Length) {
            // Добавляем символ слева обратно в diff
            char leftChar = s[l];
            if (diff.ContainsKey(leftChar)) {
                diff[leftChar]++;
                if (diff[leftChar] == 0) {
                    diff.Remove(leftChar);
                }
            } else {
                diff[leftChar] = 1;
            }
            l++;

            // Убираем символ справа из diff
            char rightChar = s[r];
            if (diff.ContainsKey(rightChar)) {
                diff[rightChar]--;
                if (diff[rightChar] == 0) {
                    diff.Remove(rightChar);
                }
            } else {
                diff[rightChar] = -1;
            }
            r++;

            // Если все символы совпали — фиксируем позицию
            if (diff.Count == 0) {
                res.Add(l);
            }
        }
        return res;
    }
}

#include <vector>
#include <unordered_map>

using namespace std;

vector<int> findAnagrams(string s, string t) {
    vector<int> res;
    if (t.size() > s.size()) {
        return res;
    }

    // diff[c] > 0 — символ нужен, diff[c] < 0 — символ лишний
    unordered_map<char, int> diff;
    for (char ch : t) {
        diff[ch]++;
    }

    int l = 0;
    int r = 0;

    // заполняем начальное окно длины len(t)
    while (r < t.size()) {
        char current = s[r];
        diff[current]--;
        if (diff[current] == 0) {
            diff.erase(current);
        }
        r++;
    }

    if (diff.empty()) {
        res.push_back(0);
    }

    // двигаем окно по строке s
    while (r < s.size()) {
        // добавляем символ слева обратно в diff
        char leftChar = s[l];
        diff[leftChar]++;
        if (diff[leftChar] == 0) {
            diff.erase(leftChar);
        }
        l++;

        // убираем символ справа из diff
        char rightChar = s[r];
        diff[rightChar]--;
        if (diff[rightChar] == 0) {
            diff.erase(rightChar);
        }
        r++;

        // если все символы совпали — фиксируем позицию
        if (diff.empty()) {
            res.push_back(l);
        }
    }
    return res;
}

package main

func findAnagrams(s string, t string) []int {
    res := []int{}
    if len(t) > len(s) {
        return res
    }

    // diff[c] > 0 — символ нужен, diff[c] < 0 — символ лишний
    diff := make(map[byte]int)
    for i := 0; i < len(t); i++ {
        diff[t[i]]++
    }

    l := 0
    r := 0

    // заполняем начальное окно длины len(t)
    for r < len(t) {
        current := s[r]
        diff[current]--
        if diff[current] == 0 {
            delete(diff, current)
        }
        r++
    }

    if len(diff) == 0 {
        res = append(res, 0)
    }

    // двигаем окно по строке s
    for r < len(s) {
        // добавляем символ слева обратно в diff
        leftChar := s[l]
        diff[leftChar]++
        if diff[leftChar] == 0 {
            delete(diff, leftChar)
        }
        l++

        // убираем символ справа из diff
        rightChar := s[r]
        diff[rightChar]--
        if diff[rightChar] == 0 {
            delete(diff, rightChar)
        }
        r++

        // если все символы совпали — фиксируем позицию
        if len(diff) == 0 {
            res = append(res, l)
        }
    }
    return res
}

import java.util.*;

public class Solution {
    public List<Integer> findAnagrams(String s, String t) {
        List<Integer> res = new ArrayList<>();
        if (t.length() > s.length()) {
            return res;
        }

        // diff[c] > 0 — символ нужен, diff[c] < 0 — символ лишний
        Map<Character, Integer> diff = new HashMap<>();
        for (char ch : t.toCharArray()) {
            diff.put(ch, diff.getOrDefault(ch, 0) + 1);
        }

        int l = 0;
        int r = 0;

        // заполняем начальное окно длины len(t)
        while (r < t.length()) {
            char current = s.charAt(r);
            diff.put(current, diff.getOrDefault(current, 0) - 1);
            if (diff.get(current) == 0) {
                diff.remove(current);
            }
            r++;
        }

        if (diff.isEmpty()) {
            res.add(0);
        }

        // двигаем окно по строке s
        while (r < s.length()) {
            // добавляем символ слева обратно в diff
            char leftChar = s.charAt(l);
            diff.put(leftChar, diff.getOrDefault(leftChar, 0) + 1);
            if (diff.get(leftChar) == 0) {
                diff.remove(leftChar);
            }
            l++;

            // убираем символ справа из diff
            char rightChar = s.charAt(r);
            diff.put(rightChar, diff.getOrDefault(rightChar, 0) - 1);
            if (diff.get(rightChar) == 0) {
                diff.remove(rightChar);
            }
            r++;

            // если все символы совпали — фиксируем позицию
            if (diff.isEmpty()) {
                res.add(l);
            }
        }
        return res;
    }
}

from typing import *
from collections import defaultdict

def find_anagrams(s: str, t: str) -> List[int]:
    if len(t) > len(s):
        return []

    # diff[c] > 0 — символ нужен, diff[c] < 0 — символ лишний
    diff = defaultdict(int)
    for ch in t:
        diff[ch] += 1

    res = []
    l = 0
    r = 0

    # заполняем начальное окно длины len(t)
    while r < len(t):
        diff[s[r]] -= 1
        if diff[s[r]] == 0:
            del diff[s[r]]
        r += 1

    if not diff:
        res.append(0)

    # двигаем окно по строке s
    while r < len(s):
        # добавляем символ слева обратно в diff
        diff[s[l]] += 1
        if diff[s[l]] == 0:
            del diff[s[l]]
        l += 1

        # убираем символ справа из diff
        diff[s[r]] -= 1
        if diff[s[r]] == 0:
            del diff[s[r]]
        r += 1

        # если все символы совпали — фиксируем позицию
        if not diff:
            res.append(l)
    return res

/**
 * @param {string} s
 * @param {string} t
 * @return {number[]}
 */
export function findAnagrams(s, t) {
  const res = [];
  if (t.length > s.length) {
    return res;
  }

  // diff[c] > 0 — символ нужен, diff[c] < 0 — символ лишний
  const diff = new Map();
  for (const ch of t) {
    diff.set(ch, (diff.get(ch) || 0) + 1);
  }

  let l = 0;
  let r = 0;

  // заполняем начальное окно длины len(t)
  while (r < t.length) {
    const current = s[r];
    diff.set(current, (diff.get(current) || 0) - 1);
    if (diff.get(current) === 0) {
      diff.delete(current);
    }
    r++;
  }

  if (diff.size === 0) {
    res.push(0);
  }

  // двигаем окно по строке s
  while (r < s.length) {
    // добавляем символ слева обратно в diff
    const leftChar = s[l];
    diff.set(leftChar, (diff.get(leftChar) || 0) + 1);
    if (diff.get(leftChar) === 0) {
      diff.delete(leftChar);
    }
    l++;

    // убираем символ справа из diff
    const rightChar = s[r];
    diff.set(rightChar, (diff.get(rightChar) || 0) - 1);
    if (diff.get(rightChar) === 0) {
      diff.delete(rightChar);
    }
    r++;

    // если все символы совпали — фиксируем позицию
    if (diff.size === 0) {
      res.push(l);
    }
  }
  return res;
}

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

Время: O(n), где n - длина s
Память: O(min(m,k)), где m - длина t, k - число уникальных символов в строках

Важно придумать решение в котором не сравниваются напрямую словарь из букв строки s и подстроки t – это red flag и не оптимально для данной задачи (так как в условии есть сноска про потенциально бесконечный алфавит).