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.
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | Kevin114514 | 3659 |
| 3 | jiangly | 3640 |
| 4 | turmax | 3450 |
| 5 | tourist | 3408 |
| 6 | strapple | 3360 |
| 7 | Um_nik | 3354 |
| 8 | squareOf105 | 3348 |
| 9 | maroonrk | 3312 |
| 10 | idontwannadothis…e | 3191 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 154 |
| 2 | nik_exists | 151 |
| 3 | maspy | 149 |
| 4 | AmShZ | 146 |
| 5 | Um_nik | 143 |
| 6 | Errichto | 139 |
| 7 | BledDest | 136 |
| 8 | adamant | 135 |
| 9 | maroonrk | 133 |
| 10 | cry | 130 |
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.
No not from a live contest, was asked in an interview.
ain't never seen an interview problem with such detailed constraints on the number of queries as well as summation over all test cases.
https://leetcode.com/discuss/interview-question/1076228/
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.