If you are not going to allow extra space, you have to compromise on time complexity..[?] If you dont have your string already stored in a trie/hashmap usage of it requires additional buffer. Simple solution would be: Sort given string using in-place sorting algorithm and then removal of duplicate characters becomes O(n). Total time complexity - O(nlogn) where n --> number of characters in the input string.
On Thu, Jun 2, 2011 at 11:17 PM, Aakash Johari <aakashj....@gmail.com>wrote:
> It was given that one or two extra variables are allowed. So I used a
> variable instead for mapping.
> It is simply mapping of each character in alphabet to a bit in the
> variable.
>
>
> On Thu, Jun 2, 2011 at 7:10 AM, Ashish Goel <ashg...@gmail.com> wrote:
>
>> using bitmap, but extra memory not allowed?
>>
>>
>> Best Regards
>> Ashish Goel
>> "Think positive and find fuel in failure"
>> +919985813081
>> +919966006652
>>
>>
>> On Thu, Jun 2, 2011 at 7:38 PM, Ashish Goel <ashg...@gmail.com> wrote:
>>
>>> what is the logic, kindly explain
>>> Best Regards
>>> Ashish Goel
>>> "Think positive and find fuel in failure"
>>> +919985813081
>>> +919966006652
>>>
>>>
>>>
>>> On Sat, May 28, 2011 at 12:23 PM, Aakash Johari
>>> <aakashj....@gmail.com>wrote:
>>>
>>>> Following code works for [A-Za-z], can be extended for whole
>>>> character-set :
>>>>
>>>>> #include <stdio.h>
>>>>>
>>>>> int main()
>>>>> {
>>>>> unsigned long long int a = 0;
>>>>> char str[50];
>>>>> int i;
>>>>>
>>>>> scanf ("%s", str);
>>>>>
>>>>> for ( i = 0; str[i]; i++ ) {
>>>>> if ( str[i] >= 'A' && str[i] <= 'Z' ) {
>>>>> if ( (a & (1ULL << (str[i] - 'A'))) == 0 ) {
>>>>> a |= (1ULL << (str[i] - 'A'));
>>>>> putchar (str[i]);
>>>>> }
>>>>> } else if ( str[i] >= 'a' && str[i] <= 'z' ) {
>>>>> if ( (a & (1ULL << (str[i] - 'a' + 26))) == 0 ) {
>>>>> a |= (1ULL << (str[i] - 'a' + 26));
>>>>> putchar(str[i]);
>>>>> }
>>>>> }
>>>>> }
>>>>>
>>>>> return 0;
>>>>> }
>>>>>
>>>>>
>>>>>
>>>> On Fri, May 27, 2011 at 11:15 PM, saurabh singh <saurabh.n...@gmail.com
>>>> > wrote:
>>>>
>>>>> string getStringWithoutDuplicateChars(string input)
>>>>> {
>>>>>
>>>>> create_empty_trie_ds (say trie)
>>>>>
>>>>> integer count = 0;
>>>>>
>>>>> for_each_char_in_string (say ch)
>>>>> {
>>>>>
>>>>> if(trie->contains(ch)) //if ch not there in ds then add it and
>>>>> return false otherwise return true
>>>>> {
>>>>> input.remove(count)
>>>>> }
>>>>>
>>>>> count++
>>>>> }
>>>>>
>>>>> return input
>>>>> }
>>>>>
>>>>> On Sat, May 28, 2011 at 11:32 AM, Rajeev Kumar <
>>>>> rajeevprasa...@gmail.com> wrote:
>>>>>
>>>>>> Design an algorithm and write code to remove the duplicate characters
>>>>>> in a string without using any additional buffer.
>>>>>> NOTE: One or two additional variables are fine.
>>>>>> An extra copy of the array is not.
>>>>>>
>>>>>>
>>>>>> --
>>>>>> Thank You
>>>>>> Rajeev Kumar
>>>>>>
>>>>>> --
>>>>>> You received this message because you are subscribed to the Google
>>>>>> Groups "Algorithm Geeks" group.
>>>>>> To post to this group, send email to algogeeks@googlegroups.com.
>>>>>> To unsubscribe from this group, send email to
>>>>>> algogeeks+unsubscr...@googlegroups.com.
>>>>>> For more options, visit this group at
>>>>>> http://groups.google.com/group/algogeeks?hl=en.
>>>>>>
>>>>>
>>>>>
>>>>>
>>>>> --
>>>>> Thanks & Regards,
>>>>> Saurabh
>>>>>
>>>>> --
>>>>> You received this message because you are subscribed to the Google
>>>>> Groups "Algorithm Geeks" group.
>>>>> To post to this group, send email to algogeeks@googlegroups.com.
>>>>> To unsubscribe from this group, send email to
>>>>> algogeeks+unsubscr...@googlegroups.com.
>>>>> For more options, visit this group at
>>>>> http://groups.google.com/group/algogeeks?hl=en.
>>>>>
>>>>
>>>>
>>>>
>>>> --
>>>> -Aakash Johari
>>>> (IIIT Allahabad)
>>>>
>>>>
>>>>
>>>>
>>>>
>>>> --
>>>> You received this message because you are subscribed to the Google
>>>> Groups "Algorithm Geeks" group.
>>>> To post to this group, send email to algogeeks@googlegroups.com.
>>>> To unsubscribe from this group, send email to
>>>> algogeeks+unsubscr...@googlegroups.com.
>>>> 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 algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>
>
> --
> -Aakash Johari
> (IIIT Allahabad)
>
>
>
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> 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 algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
<<33D.gif>>
