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.
