werewolf97's blog

Need help with this
By werewolf97, history, 4 years ago, In English

Given a string A. You need to solve Q queries. In each queries, you will be given a string B[i]. You need to find the count of the number of substrings of A which are anagrams of B[i].

Contraints:

1<=|A|, |B[i]|<=10^5 1<=Q<=10^5 summation|B[i]|<=2x10^5 All the strings consists of lowercase English letters.

  • Vote: I like it
  • +2
  • Vote: I do not like it

Comments Comments (5)
| Write comment?
»
4 years ago, # |
  Vote: I like it +31 Vote: I do not like it

Provide a link to the statement or say where is this problem from, if you don't do this, i can't know if this problem is from a ongoing contest or not.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    No not from a live contest, was asked in an interview.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +35 Vote: I do not like it

      ain't never seen an interview problem with such detailed constraints on the number of queries as well as summation over all test cases.

      → Reply
»
4 years ago, # |
  Vote: I like it +11 Vote: I do not like it

https://leetcode.com/discuss/interview-question/1076228/

→ Reply
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

There are 1000 different values of len(B[i]) in Q queries. For each different value of len(B[i]), Iterate through A and store in map the cnt 26 length array of freq cnt for the length of substring. This takes O(1000*len(A)) and final ans can be done in O(1) per query.

→ Reply