Given a string S and Q queries. Each query contains two integers M and P. The task is to find count number of strings of length M that occur exactly P times as substrings in S.
In the on-campus test, the constraints were S.length()<=10^3, so I wrote a code, preprocessing each substring using a map in O(N^2) and answered each query in O(1) and it passed.
Does it have some more optimal approach of O(N) or O(N*logN) if S.length()<=10^5 ?
Since it was on-campus drive, I don’t have a link to the problem statement.
The best I can think of is using a trie/suffix tree and the preprocesing, but even there, the O(n^2) remains, as I am iterating through every substring. Your problem basically asks us to find a technique to work on all substrings without actually iterating though them. I have no idea how to optimize that, so I don’t think I know how to solve this problem.
I hope the others u have tagged shed some light on this.