assuming lower case characters.
#include <iostream>
#include <string>
#include <limits.h>
#include <string.h>
using namespace std;
int main ()
{
unsigned int x,y;
int ar[26];
string s;
cin >> s;
x = 0;
y = 0;
int l;
int min = INT_MAX;
unsigned int i = 0;
memset(ar,-1,sizeof(ar));
for(i = 0; i < s.size(); i++)
{
l = s[i] - 'a';
/*first occurrence*/
if(!((1 << (l)) & x))
{
ar[l] = i;
x = x|(1 << l);
}
else {
y = y|(1 << l);
}
}
//cout << x << " " << y << endl;
for(i = 0; i < 26; i++)
{
// cout << ar[i] << endl;
if(ar[i] == -1)
continue;
if(min > ar[i] && (!((1<<i)&y))) {
min = ar[i];
l = i;
}
}
cout << (char) (l + 'a') << endl;
return 0;
}
On Mon, Jul 18, 2011 at 7:55 PM, shady <[email protected]> wrote:
> "Any possible o(1) space o(n) soln?"
> O(1) space and O(n) time complexity ?
>
>
> On Mon, Jul 18, 2011 at 7:46 PM, saurabh singh <[email protected]>wrote:
>
>> In that case only the size of hash table will be required to increase.Any
>> possible o(1) space o(n) soln?
>>
>>
>> On Mon, Jul 18, 2011 at 7:43 PM, shady <[email protected]> wrote:
>>
>>> O(n) for both space and time.......
>>> count the number of times each character is coming = O(n) space in worst
>>> case
>>> start from the string beginning if character has count == 1 print it O(n)
>>> in worst case
>>> this works with ASCII characters... since we can hash them on their
>>> values 0, 255.......... for languages like hindi, german don't know :)
>>>
>>>
>>> On Mon, Jul 18, 2011 at 7:35 PM, hary rathor <[email protected]>wrote:
>>>
>>>> can anybody tell me in O(n) solution,?
>>>>
>>>>
>>>> --
>>>> 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.
>>>
>>
>>
>>
>> --
>> Saurabh Singh
>> B.Tech (Computer Science)
>> MNNIT ALLAHABAD
>>
>>
>>
>> --
>> 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.
>
--
Varun Pahwa
B.Tech (IT)
7th Sem.
Indian Institute of Information Technology Allahabad.
Ph : 09793899112
Official Email :: [email protected]
Another Email :: [email protected]
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 [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.
