@sagar ur solution is very gud...bt wat abt blank spaces and capital
alphabets dat may be thr...i dnt think it will take care of that...
On Mon, Jul 18, 2011 at 11:32 PM, varun pahwa <varunpahwa2...@gmail.com>wrote:
> @sagar: that's what i have done i have taken two variables x and y which
> can show if repetition is there or not. and we can store the initial
> positions in the array in that case u don't have to traverse the string
> twice.
>
>
> On Mon, Jul 18, 2011 at 10:33 PM, sagar pareek <sagarpar...@gmail.com>wrote:
>
>> @dumanshu
>> first read my soution just above yours :)
>>
>> On Mon, Jul 18, 2011 at 10:21 PM, Dumanshu <duman...@gmail.com> wrote:
>>
>>> heres my solution with TC O(n) and SC O(26)
>>> input string str
>>> int arr[26] = {0};
>>> traverse the string, character by character and increment the
>>> corresponding counter.
>>> i.e. arr[str[i]]++;
>>>
>>> Now traverse the string again and print out the first character
>>> encountered whose arr[str[i]] == 1;
>>>
>>> On Jul 18, 9:20 pm, sagar pareek <sagarpar...@gmail.com> wrote:
>>> > Very good solution :- but space complexity = O(26)
>>> >
>>> > take integer array arr[0-25] and initialise it with 0 by taking it
>>> static
>>> > logic is that we have only 26 characters so if i want to map character
>>> 'a'
>>> > with 0th position of arr[] then it can be done as atoi('a')-97.
>>> > so whenever we encounter any character say str[i] (where str is array
>>> of
>>> > given string) then it can be incremented as arr[atoi(str[i])-97]++
>>> > so traverse the whole str[] and increment the corresponding values .
>>> > At the end those characters which never encounter have values 0 in arr
>>> ,
>>> > which encounter only once have values 1 and more than once have
>>> values>1.
>>> > at the end traverse the whole arr[] and find out the corresponding
>>> character
>>> > as itoa(arr[i]+97) :) :)
>>> >
>>> > But we have to do extra work to find the first character which repeats
>>> only
>>> > once
>>> >
>>> > On Mon, Jul 18, 2011 at 8:09 PM, hary rathor <harry.rat...@gmail.com>
>>> wrote:
>>> > > can we use bit vector ?
>>> > > because by do it we need just 32 bits of one extra variable .
>>> >
>>> > > --
>>> > > 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.
>>> >
>>> > --
>>> > **Regards
>>> > SAGAR PAREEK
>>> > COMPUTER SCIENCE AND ENGINEERING
>>> > NIT 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.
>>>
>>>
>>
>>
>> --
>> **Regards
>> SAGAR PAREEK
>> COMPUTER SCIENCE AND ENGINEERING
>> NIT 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.
>>
>
>
>
> --
> Varun Pahwa
> B.Tech (IT)
> 7th Sem.
> Indian Institute of Information Technology Allahabad.
> Ph : 09793899112
> Official Email :: rit2008...@iiita.ac.in
> Another Email :: varunpahwa.ii...@gmail.com
>
> People who fail to plan are those who plan to fail.
>
> --
> 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.
>
--
Aditi Garg
Undergraduate Student
Electronics & Communication Divison
NETAJI SUBHAS INSTITUTE OF TECHNOLOGY
Sector 3, Dwarka
New Delhi
9718388816
--
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.
