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.
