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 <sinv...@gmail.com> 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 <saurab...@gmail.com>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 <sinv...@gmail.com> 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 <harry.rat...@gmail.com>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 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. >>> >> >> >> >> -- >> 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 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. > -- 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.