But generating a suffix tree itself is O(n2) .
On Tue, Jun 14, 2011 at 7:54 PM, sunny agrawal <[email protected]>wrote: > it must be any general string > Suffix tree approach seems best both in time and space complexity > > > > > On Tue, Jun 14, 2011 at 7:36 PM, Navneet Gupta <[email protected]>wrote: > >> This looks like a good problem. Could you confirm if string contains only >> two characters as you mentioned in both examples or it is a general string >> with any characters. >> >> >> On Tue, Jun 14, 2011 at 6:33 PM, bittu <[email protected]>wrote: >> >>> I found one interesting question >>> >>> Given a string s , return the shortest substring that is >>> only occurring once. >>> Examples: >>> s="aabbabbaab" gives either "bab" or "baa" >>> s="aaaa" gives "aaaa" >>> >>> My Approaches >>> >>> Generate All Possible SubStrings O(N^2) >>> puts all substrings into hashtable & keep incrementing counter for >>> each substring , return substring with counter 1 memory O(N) >>> Not efficient >>> >>> Create Suffix Tree Seems to be Efficient Solution Only You Need to do >>> Create Tree & then we can find the >>> shortest substring that is only occurring once. in O(n) time >>> >>> PS: let me other approaches,suggestion >>> >>> Thanks >>> Shashank >>> CSE,BIT Mesra >>> >>> -- >>> You received this message because you are subscribed to the Google Groups >>> "Algorithm Geeks" group. >>> To post to this group, send email to [email protected]. >>> To unsubscribe from this group, send email to >>> [email protected]. >>> For more options, visit this group at >>> http://groups.google.com/group/algogeeks?hl=en. >>> >>> >> >> >> -- >> --Navneet >> >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to [email protected]. >> To unsubscribe from this group, send email to >> [email protected]. >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> > > > > -- > Sunny Aggrawal > B-Tech IV year,CSI > Indian Institute Of Technology,Roorkee > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- AKSHAY RASTOGI BE(Hons) CS BITS PILANI , Pilani -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
