We can do it in just one pass. Start scanning the array and whichever element gets scanned just store some kind of marker in the additional array that this element has been vsisted.Next time you get some element if that element (or character) is not visited earlier than mark it as visited and print it or if it was visited earlier just skip it.
On Fri, Aug 5, 2011 at 8:30 PM, nishaanth <[email protected]> wrote: > Store the frequency of all the letters in an array in one scan(like > counting sort). In the next pass remove the duplicates and appropriately > shift . takes 2 O(n) passes i guess.... > > > On Fri, Aug 5, 2011 at 4:50 PM, priya v <[email protected]> wrote: > >> >> Remove duplicate alphabets from a string and compress it in the same >> string. For >> example, MISSISSIPPI becomes MISP. O (n2) is not acceptable. >> For this problem is it a good idea to sort the array using a sorting >> technique with efficiency O(nlogn) >> and remove the duplicates? >> >> -- >> 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. >> > > > > -- > S.Nishaanth, > Computer Science and engineering, > IIT Madras. > > -- > 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. > -- 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.
