CareerCup

Improvinf T's orignal code and taking other's comment

char Nrc (char *str)
{
   int HashTable[256] = {0};
   char *tmp = NULL;

   // if the string is empty or parameter is NULL, return not found
   if(!str || !*str)
      return 0;

   tmp = str;
   while(*tmp)
      HashTable[*tmp++]++;
   
   tmp = str;
   while(NULL != *tmp && 1 =! HashTable[*tmp])
      tmp++;
   return *tmp; // Would take care of found/not found (returning the last char-NULL)
}

#include<stdio.h>
char nrc(char *s)
{
int flag;
char *p;
while(*s)
{
flag=0;
p=s;
p++;
if(*s!='#')
{
while(*p)
{
if(*s==*p)
{
*p='#';
flag=1;
}
p++;
}
if (flag==0)
return *s;
}
s++;
}
}
int main()
{
char str[]="teeter";
char j=nrc(str);
printf("first non repeated character is %c\n",j);
return 0;
}

The above algorithm is O(N^2). This can be done in O(N) time and O(1) space.

char nrc(char *s) {

    int hashTable[256];
    int i;
    char *tmp;

    if (s == NULL) { return '\0';}

    for (i = 0; i < 256; i++) { hashTable[i] = 0;}

    tmp = s;

    while (tmp != NULL) {

        hashTable[*tmp]++;
        tmp++;
    }
    
    for (i = 0; i < 256; i++) {

        if (hashTable[i] == 1) {
            return (char)i;
        }
    }

    return '\0';
}

T: Unfortunally your solution returns the non-repetitive char with the loweest ASCII number, Not the FIRST non-repetitive char.

For example: dbdcaecdf
Your method would return 'a', not 'b'.
Because:
for (i = 0; i < 256; i++) {

if (hashTable[i] == 1)
{ return (char)i; }
}

char Non_rep(const string& str)
{
if (str==null) return 1;

typedef string::const_iterator striter;
striter it= str.begin();
map<char, int> counter;
while (it!= str.end())
{
++counter[*it];
++it;
}


for (map<char, int>::const_iterator mapiter=counter.begin(); mapiter!=counter.end(); ++mapiter)
{
if (mapiter->second==1)
return mapiter->first;
}
cout<<"all dup"<<endl;
};

Hi VFeng,

Map container internally keeps a sorted list of keys. In your code the char will
be always in sorted order. Again as mentioned earlier by "kulang" you will get the
non-rep char with lowest ascii value. please correct me if i am wrong. thanks

char
find_nonrepetitive(const string& in) 
{
        map<char, int> h_table;
        string :: const_iterator it; 
    
        for (it = in.begin(); it != in.end(); it++)
            h_table[*it]++;

        for (it = in.begin(); it != in.end(); it++)
            if (h_table[*it] == 1)
                return (*it);

        return (NO_REPEAT);
}

Let the number of elements be n, assuming case insensitive problem.
O(n) time to hash it on the hash table.
O(26) to find the first slot with minimum index non-negative value.

- Stores the index on the hash table
- Set the hash table value to -1 on collision

Three types of Hash values
a. -2 , Initial value, implies no hashed value on this index.
b. -1 , more than 2 occurrences found.
c. Index, which implies a single occurrence so far.

Improvinf T's orignal code and taking other's comment

char Nrc (char *str)
{
   int HashTable[256] = {0}; //initialize array with zero 
   char *tmp = NULL;

   // if the string is empty or parameter is NULL, return not found
   if(!str || !*str)
      return 0;

   tmp = str;
   while(*tmp)
      HashTable[*tmp++]++;
   
   tmp = str;
   while(NULL != *tmp && 1 =! HashTable[*tmp])
      tmp++;
   return *tmp; // Would take care of found/not found (returning the last char-NULL)
}

If your code has "silly bug", it may not be hard to correct it. If your ALGORITHM has a "silly" or "non-silly" bug, it is a disaster! It means your ALGORITHM worths nothing, zero, zip! Asumming it does cause problem.

Here is a algorithm. Assuming we are dealing with on a, b, c, d, and e five characters.
Also assuming we are dealing with long strings: dddcdd

1. Exam first six chars "dddcdd", so we have at least one repeat char(d). If we find one non-repeat on, say 'c', we store it in non-repeat candidate pair array NP(char, index), So, we have NP(0) = ('c', 4). We also store d in RP array: RP(0) = 'd'.

2. Get next................. ++++

If your code has "silly bug", it may not be hard to correct it. If your ALGORITHM has a "silly" or "non-silly" bug, it is a disaster! It means your ALGORITHM worths nothing, zero, zip! Asumming it does cause problem.

Here is a algorithm. Assuming we are dealing with on a, b, c, d, and e five characters.
Also assuming we are dealing with long strings: dddcdd

1. Exam first six chars "dddcdd", so we have at least one repeat char(d). If we find one non-repeat on, say 'c', we store it in non-repeat candidate pair array NP(char, index), So, we have NP(0) = ('c', 4). We also store d in RP array: RP(0) = 'd'.

2. Get next................. ++++

T's code is simple and working, ignoring those stupid/silly bugs...the question itself is pretty simple...

Searching the hash table for count=1 would find a nonrepeated character, but it wouldn’t necessarily be the first one in the original string.

Therefore, you need to search your count values in the order of the characters in the original string. Just look up the count value for each character until you find a 1. When you find a 1, you’ve located the first nonrepeated character and you break from the algorithm.

In the worst case, we might have to look up the count value for each character in the string to find the first nonrepeated character. Hash/Array lookup is O(1), the worst case would be two operations for each character in the string, giving 2n, which is still O(n).

char * FindFirstNonRepeat(char *s){
char * tmp = *s;
char a[256] = {0};

while(!s){
	a[*s]++;
	s++;
}

While(!tmp){
	If(a[*tmp]==1) return *tmp
	Tmp++;
}
Return -1;
}

no need for a map/vector/?? when a simple array can do it.

How about implementing it using priority search tree? The operation to find the first non-repetitive character would correspond to

minXinRectangle(0, strlen(input_str)-1, 1)

in that case the complexity would be O(log n).

If you insist on O(n), then a much convoluted way of doing this would be to create 2 data structures - 1. hash table indexed by ascii which contains count; 2. a temporary array storing the unique characters(not necessarily non-repetitive) in the order they show up. Then what we do is

void find_and_print_first_non_repetitive_char(char s[])
{
int* temp = (int*) malloc(strlen(s) * sizeof(int));
int table[256];
int j = 0;

for (int i = 0;i < strlen(s);i++)
{
char c = s[i];
if (table[c] == 0)
{
temp[j++] = (int)c;
table[c]++;
}
}

for (int i = 0;i < j;i++)
{
if (temp[i] == 1)
{
printf("first non-repetitive character: %c\n", temp[i]);
}
}
}

Java implementation using LinkedHashMap.

import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.Map;

public class FirstNonRepetetive {
	public static void main(String[] args) {
		String s = "teeterra";
		System.out.println("FirstNonRepetetive:"
				+ getFirstNonRepetetiveCharacter(s));
	}

	private static char getFirstNonRepetetiveCharacter(String string) {
		Map<Character, Integer> map = new LinkedHashMap<Character, Integer>();
		char c;
		for (int i = 0; i < string.length(); i++) {
			c = string.charAt(i);
			if (map.get(c) == null) {
				map.put(c, 1);
			} else {
				map.put(c, map.get(c) + 1);
			}
		}
		Iterator<Character> keys = map.keySet().iterator();
		char key = 0;
		boolean found = false;
		while (keys.hasNext()) {
			key = keys.next();
			if (map.get(key) == 1) {
				found = true;
				break;
			}
		}

		if (found) {
			return key;
		} else {
			return 0;
		}
	}
}

Do it easy way!!

O(n) with O(1) space complexity
take a temp variable temp=0.
scan the string from beginning and keep on XORing the value with temp. the moment you get the XOR as non zero after the first time after when you did temp <XOR> str[0], is the first non repeating value!!