Pythonic Substring Anagram Index

Question

I'm working on improving my Python skills and have been doing a daily code problem. For the problem:

Given a word W and a string S, find all starting indices in S which are anagrams of W

For example s = "abxaba" and w = "ab" should return [0, 3, 4], s = "cbaebabacd", w = "abc" should return [0, 6]

Is there more efficient/pythonic solution than the code I wrote? Storing the queue as a list and casting it to set twice per loop feels like it must be inefficient.

def anagram_indices(w, s):

  w = set(list(w))

  queue = []
  index = []

  for x, i in enumerate(list(s)):
    queue.append(i)

    while(w.issubset(set(queue[1:]))):
      queue.pop(0)

    if w == set(queue):
      index.append(x-len(w)+1)

  return(index)

word = "ab"
string = "abxaba"

print(anagram_indices(word, string))

Answer 1

index is a singular noun that doesn't represent of group of things, therefor it isn't a good name for an array.

Your method is named anagram_indices and returns an array, I like to call the returned array results, so it's clear that the array are the anagram indices.

Using i and x is very confusing, so much that it made me question my own knowledge of the enumerate function. I expected i to be the index and x to be the letter, while it's the opposite. You should rename those with better variable names. Actually, using single letter variable names is almost never a good idea, there are some edge cases. I expect a variable named i to represent an index, for example.

Your algorithm itself is fine, but the naming is very confusing, which is kind of a problem.

Answer 2

list

A str is an iterable itself, so calling list on it in w = set(list(w)) and for x, i in enumerate(list(s)): is unnecessary.

set

a set only has the unique elements. If the word w contains any double letters, they will be only counted once. A Counter is a more appropriate data structure

deque

For the queue, a deque (double ended queue) would be a better data structure then a list for additions on one end, and pops on the other. If you define the maxlen, you don't even need to explicitly pop.

generators

You can forgo the index list, and instead yield the index at which there is an anagram

def anagram_indices2(w, s):
    len_w = len(w)
    if len_w > len(s):
        return # or raise an Exception
        # raise ValueError("`w` must not be at longer than `s`")

    word_counter = Counter(w)
    queue = deque(s[:len_w-1], maxlen=len_w)

    for i, char in enumerate(s[len_w-1:]):
        queue.append(char)
        if Counter(queue) == word_counter:
            yield i

The s[:len_w-1] is so you don't have to make a separate check for the first round of words

Which gives:

 list(anagram_indices2(word, string))

[0, 3, 4]

 list(anagram_indices2("abab", "abxbabas"))

[3]