Help needed in Wipro Oncampus problem

general
, , , ,
#1

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.

1 Like
#2

Hi, can you share all the constraits (with the time and space limits)?

Also, with a suffix tree you can have a preprocessing in O(NlogN) and each query answered in O(NlognN).
O(QNLogN) at the end.

#3

Hi. The constraints were as follows.
S.length()<=10^3
Time limit per test - 1 second

Also, can you please elaborate on the preprocessing using suffix trees and suggest some resources too on the topic if possible.
Thanks.

#4

But i think again it is not optimal , if Q = 105 then TLE , we have to something else , @carre @tamo11 @ssjgz @everule1 also help me in thiss .

#5

But remember that using a map for string is more than O(N^2), even more than O(N^2logN), bc there is a comparison between substrings

but with a suffix tree, it can run exactly in O(N^2) for preprocessing + O(1) per query (just saying, ik that is not optimal, for the new constraits)

#6

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.

1 Like