CareerCup

I came up with the following solution:
Its single pass and uses optimal data structures to avoid subloops.

The idea is:
Maintain a Hashmap of <Character, Integer> which stored how many time a character has appeared as we traverse.

The LinkedHashSet maintains a LinkedList of characters in the order they have appeared.
If any character has re-appeared (count of it in Hashmap > 1) while scanning remove it from LinkedHashSet , which is O(1) operation.
The motivation to use this is final lookup operation to get the first non repeating character is O(1).
If it appeared first time add to the LinkedHashSet (the datastructure will add it to the end of underlying LinkedList) and add to HashMap with count 1.
Thus this LinkedHashSet stores only characters which have appeared once in the order they appear in the string.

At the end of scan of string print the first character from the LinkedHashSet as it will the element which has appeared only once and also it has appeared first. Thus its the First Non Repeating Character.

public static void findFirstNonRepeating {

		String s = "abbaad";

		LinkedHashSet<Character> lhs = new LinkedHashSet<Character>();
		HashMap<Character, Integer> hm = new HashMap<Character, Integer>();

		for (char c : s.toCharArray()) {
			if (hm.get(c) != null) {
				Integer occ = hm.get(c);
				hm.put(c, ++occ);
				if (++occ > 1) {
					//O(1) operation
					lhs.remove(c);
				}
			} else {
				//O(1) operation
				hm.put(c, 1);
				lhs.add(c);
			}
		}
	        //O(1) operation		
		Iterator<Character> itr = lhs.iterator();
		while(itr.hasNext()){
			System.out.println(itr.next());
			break;
		}
	}

Let's keep a secondary array that will tell us whether the character at the index has a copy.

We will also keep a hashtable, call it h, with key value pair of this <char, indices of char>.

Finally keep a pointer on the secondary array.

We pass through the list and add characters to the hashtable. If there is already a value for the key to that char, we set the position in the secondary array to 1. If we set a value to 1 and the secondary array pointer is pointing there, we increment this pointer until it points to a 0.

at the end, return the character at the position the pointer is pointing to.

Some code:

public char firstUnique(String s) {
	

	HashMap<Character, ArrayList<Integer>> h = new HashMap<Character, ArrayList>();

	int[] valid = new int[s.length()];
	int ptr = 0;
	char currentChar;

	for (int i = 0; i < s.length(); i++) {

		currentChar = s.charAt(i);

		if (!isUnique(currentChar, i, h, valid)) {

			for (Integer i : h.get(currentChar)) {

				if (i == ptr) {

					while (arr[ptr++] != 0) {}
				}
			}
		}
	}

	if (ptr >= s.length()) {

		return '';
	}

	return s.charAt(ptr);
}

public boolean isUnique(char c, int currIndex, HashMap h, int[] arr) {
		

	if (h.exists(c)) {


		h.get(c).add(currIndex);
		arr[currIndex] == 1;
		return true;
	}

	ArrayList<Integer> toAdd = new ArrayList<Integer>();
	toAdd.add(currIndex);
	h.put(c, toAdd);
	return false;
}

public int find(String str){
		
		int leng =str.length();
		Map<String, Integer> poses = new HashMap();
		for(int i=0; i<str.length();i++){
			String c = str.substring(i, i+1);
			if(poses.containsKey(c)){
				int tmp = (int) poses.get(c);
				poses.put(c, tmp+leng );
			}else{
				poses.put(c, i);
			}
		}
		int minPos = 1000;
		String s;
		for (String key : poses.keySet() ) {
		   if( poses.get(key) < minPos ){
			   minPos = poses.get(key);
			   s = key;
		   }
		}
		
		return minPos;
		
	}

from my understanding isUnique returns true when it's not unique and false when it is
wrong naming??

s=raw_input()

li=[]
d={}
for l in s:
	if l not in li:
		li.append(l)
	d[l]=d.get(l,0)+1

for l in li:
	if d[l]==1:
		print l
		break

here is the logic:
1. maintain two 256 char tables one to keep count of char occurrence.
2. second to store chars as per their indexes in the string, skip chars occurring more than once.
3. traverse second array and check the char's count in first arr if it's one, you got first non-repeating char.

void findFirstNonRepeatedCharSinglePass()
{
	string str = "tis is thesk";
	char charMap[256] = { 0 };
	char charIndx[256] = {' '};
	for (int i = 0; i < str.size(); i++) {
		//if the char is already duplicate we we can avoid it adding into charindex
		if (charMap[str[i]] == 0){
			charIndx[i] = str[i];
		}
		charMap[str[i]]++;
	}
	for (int i = 0; i < 256; i++) {
		char ch = charIndx[i];
		if (ch != ' ' && charMap[ch] == 1) {
			cout << "First non-repeated char " << ch;
			break;
		}
	}
}

import java.util.ArrayList;

class SolutionForFindFirstNonRepeatingCharInSinglePass {

    public String firstNonRepeatingChar(String str) {
        if(str.length() == 0) {
            return "";
        }
        ArrayList<Character> temp = new ArrayList<Character>();
        boolean[] charmap = new boolean[256];
        for (int i = 0; i < str.length(); i++) {
            int val = str.charAt(i);
            if (!charmap[val]) {
                temp.add(str.charAt(i));
                charmap[val] = true;
            } else {
                if (temp.size() != 0) {
                    temp.remove((Character) str.charAt(i));
                }
            }
        }

        if (temp.size() == 0) {
            return "";
        }
        return temp.get(0) + "";
    }
}

public class FindFirstNonRepeatingCharInSinglePass {

    public static void main(String[] args) {
        SolutionForFindFirstNonRepeatingCharInSinglePass sol = new SolutionForFindFirstNonRepeatingCharInSinglePass();
        System.out.println("1.INPUT: aaaaaaaaaaa ANS: " + sol.firstNonRepeatingChar("aaaaaaaaaaa"));
        System.out.println("2.INPUT: \"\" ANS: " + sol.firstNonRepeatingChar(""));
        System.out.println("3.INPUT: aabbccd ANS: " + sol.firstNonRepeatingChar("aabbccd"));
        System.out.println("4.INPUT: aabcbcba ANS: " + sol.firstNonRepeatingChar("aabcbcba"));
        System.out.println("5.INPUT: aabcbcbe ANS: " + sol.firstNonRepeatingChar("aabcbcbe"));
        System.out.println("6.INPUT: abcde ANS: " + sol.firstNonRepeatingChar("abcde"));
        System.out.println("7.INPUT: abcbcbae ANS: " + sol.firstNonRepeatingChar("abcbcbae"));
        System.out.println("8.INPUT: abcbedcbae ANS: " + sol.firstNonRepeatingChar("abcbedcbae"));
        System.out.println("9.INPUT: abcbedcbfae ANS: " + sol.firstNonRepeatingChar("abcbedcbfae"));
    }
}

public static Character firstUnqiue(String str) {
		Map<Character, Integer> occRecorder = new LinkedHashMap<Character, Integer>();
		for (char c : str.toCharArray()) {
			if (occRecorder.get(c) == null) {
				occRecorder.put(c, 1);
			} else {
				occRecorder.put(c, occRecorder.get(c) + 1);
			}
		}

		for (Character key : occRecorder.keySet()) {
			if (occRecorder.get(key) == 1) {
				return key;
			}
		}
		return null;
	}

/*Solution: 1. Create a LinkedHashSet "set" that stores the Characters
* 2. Loop through the String.
* 3. Check if the ascii array has true for that character.
* 4. If yes then check if set contains the character. If yes then remove it.
*
* 3-b) If ascci array is false for that Character mark it true and add it to the set.
*
* 5. After the loop return the first element in the set if size of set > 0
*
* */

public static void problem3()
{
//String input = "tis ils khesktplhe";
String input = "abcedbacc";

Set<Character> set = new LinkedHashSet<>();
boolean[] ascii = new boolean[256];
for(char ch : input.toCharArray())
{
int index = (int) ch;
if(ascii[index])
{
if(set.contains(ch))
{
set.remove(ch);
}
}
else
{
ascii[index] = true;
set.add(ch);
}
}

for(Character ch : set)
{
System.out.println(ch);
break;
}
}

My solution is: I am going to use a HashMap to keep a frequency (counter) and a LinkedHashSet to keep the characters ordered by its insertion.

Every time I detect a frequency = 2, I am going to remove from the LinkedHashSet.
In the end, just the characters presented once will remain sorted by insertion time.

import java.util.*;

/**
 * Created by sky on 4/19/15.
 */
public class FirstNonRepeatedCharacter {
    private static class Counter {
        private int counter;

        public Counter(int initial) {
            this.counter = initial;
        }

        public void increment() {
            this.counter++;
        }

        @Override
        public String toString() {
            return "[" + this.counter + "]";
        }
    }

    public static void main(String[] args) {
        String s = "abcdeabc";
        Map<Character, Counter> freq = new HashMap<>();
        Set<Character> nonRepeated = new LinkedHashSet<>();

        for (int i = 0; i  < s.length(); i++) {
            Character chr = s.charAt(i);
            Counter c = freq.get(chr);
            if (c != null) {
                c.increment();
                if (c.counter == 2) {
                    nonRepeated.remove(chr);
                }
            } else {
                freq.put(chr, new Counter(1));
                nonRepeated.add(chr);
            }
        }


        Iterator it = nonRepeated.iterator();
        if (it.hasNext())
            System.out.println("First non repeated: " + it.next());
    }
}

using System;

public class Program
{
public static void Main()
{
string str="sartsddaslkdjkasndalnsdaklmdnklnslrtjqdsdfnldsfmlsmflsmldfmsldfmldsmflsdmflsmlfmlsdmflsmdlfmsldmflsdmlfmsdlfmlsdmlfmsdlkflsmlfmsldmflsdlf";
Char[] cs=new Char[str.Length];
cs=str.ToCharArray();
int[] item=new int[cs.Length];


for(int i = 0 ; i<cs.Length;i++)
{
int count=0;

for(int j = 0 ; j<cs.Length;j++)
{
if(str[i] == cs[j])
{
count=count+1;
}
}
item[i]=count;
}
for(int k=0;k<item.Length;k++)
{
if(item[k]==1)
{
System.Console.WriteLine(cs[k]);
break;
}
}

}
}

using System;

public class Program
{
public static void Main()
{
string str="sartsddaslkdjkasndalnsdaklmdnklnslrtjqdsdfnldsfmlsmflsmldfmsldfmldsmflsdmflsmlfmlsdmflsmdlfmsldmflsdmlfmsdlfmlsdmlfmsdlkflsmlfmsldmflsdlf";
Char[] cs=new Char[str.Length];
cs=str.ToCharArray();
int[] item=new int[cs.Length];


for(int i = 0 ; i<cs.Length;i++)
{
int count=0;

for(int j = 0 ; j<cs.Length;j++)
{
if(str[i] == cs[j])
{
count=count+1;
}
}
item[i]=count;
}
for(int k=0;k<item.Length;k++)
{
if(item[k]==1)
{
System.Console.WriteLine(cs[k]);
break;
}
}

}
}

using System;

public class Program
{
public static void Main()
{
string str="sartsddaslkdjkasndalnsdaklmdnklnslrtjqdsdfnldsfmlsmflsmldfmsldfmldsmflsdmflsmlfmlsdmflsmdlfmsldmflsdmlfmsdlfmlsdmlfmsdlkflsmlfmsldmflsdlf";
Char[] cs=new Char[str.Length];
cs=str.ToCharArray();
int[] item=new int[cs.Length];


for(int i = 0 ; i<cs.Length;i++)
{
int count=0;

for(int j = 0 ; j<cs.Length;j++)
{
if(str[i] == cs[j])
{
count=count+1;
}
}
item[i]=count;
}
for(int k=0;k<item.Length;k++)
{
if(item[k]==1)
{
System.Console.WriteLine(cs[k]);
break;
}
}

}
}

using System;
	
public class Program
{
	public static void Main()
	{
		string str="sartsddaslkdjkasndalnsdaklmdnklnslrtjqdsdfnldsfmlsmflsmldfmsldfmldsmflsdmflsmlfmlsdmflsmdlfmsldmflsdmlfmsdlfmlsdmlfmsdlkflsmlfmsldmflsdlf";
		Char[] cs=new  Char[str.Length];
		cs=str.ToCharArray();
		int[] item=new int[cs.Length];
		
		
		for(int i = 0 ; i<cs.Length;i++)
		{
			int count=0;
			
			for(int j = 0 ; j<cs.Length;j++)
			{
				if(str[i] == cs[j])
				{
					count=count+1;
				}
			}
			item[i]=count;
		}
		for(int k=0;k<item.Length;k++)
		{
			if(item[k]==1)
			{
				System.Console.WriteLine(cs[k]);
				break;
			}
		}
			
	}

}

using System;

public class Program
{
public static void Main()
{
string str="sartsddaslkdjkasndalnsdaklmdnklnslrtjqdsdfnldsfmlsmflsmldfmsldfmldsmflsdmflsmlfmlsdmflsmdlfmsldmflsdmlfmsdlfmlsdmlfmsdlkflsmlfmsldmflsdlf";
Char[] cs=new Char[str.Length];
cs=str.ToCharArray();
int[] item=new int[cs.Length];


for(int i = 0 ; i<cs.Length;i++)
{
int count=0;

for(int j = 0 ; j<cs.Length;j++)
{
if(str[i] == cs[j])
{
count=count+1;
}
}
item[i]=count;
}
for(int k=0;k<item.Length;k++)
{
if(item[k]==1)
{
System.Console.WriteLine(cs[k]);
break;
}
}

}
}

/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
		String input = "abbaad";
		
		// to hold unique characters in string
		ArrayList<Character> al = new ArrayList<Character>();
		
		// to hold duplicate characters in string
		ArrayList<Character> bl = new ArrayList<Character>();
		for(int i = 0; i < input.length(); i++){
			
			if(bl.contains(input.charAt(i))){
					al.remove(new Character(input.charAt(i)));
			}
			else{
					al.add(new Character(input.charAt(i)));
					bl.add(new Character(input.charAt(i)));
			}
			
		}
		System.out.println("First non-repeating character is "  +al.get(0));
	}
}

/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
public static void main (String[] args) throws java.lang.Exception
{
String input = "abbaad";
ArrayList<Character> al = new ArrayList<Character>();
ArrayList<Character> bl = new ArrayList<Character>();
for(int i = 0; i < input.length(); i++){

if(bl.contains(input.charAt(i))){
al.remove(new Character(input.charAt(i)));
}
else{
al.add(new Character(input.charAt(i)));
bl.add(new Character(input.charAt(i)));
}

}
System.out.println("First non-repeating character is " +al);
}
}

This C++ version has just one loop, however uses std::remove which might be doing some looping on the non_repeating char vector.

char find_first_nonrepeating(const std::string& str) {
  std::map<char, int> index_map;
  std::vector<char> vec;

  for (auto ch : str) {
    auto it = index_map.find(ch);
    if (it == index_map.end()) {
      vec.push_back(ch);
      index_map.insert(std::pair<char,int>(ch, static_cast<int>(vec.size())));
    } else {
      int it2 = it->second;
      if (it2 != -1) {
	vec.erase(std::remove(vec.begin(), vec.end(), ch), vec.end());
	index_map[ch] = -1;
      }
    }
  }
  if (vec.size())
    return vec[0];
  else
    return '\0';
}

utilize a dynamic list-like structure, i.e. a set in python. Have two sets, values we know are repeated, and values weve only seen once so far.

As you traverse the characters in the string, check to see if char x (the current char) is already in the set of values we know repeat, if so, skip it. If x is in the set of values weve only seen once, add x to the set of repeating vals and remove it from the unseen set. Otherwise, just add it to set of unseen values.

in python:

def find_non_rep(word):
	seen_vals = set()
	unseen_vals = set()
	for x in word:
		if x in seen_vals:
			continue
		elif x in unseen_vals:
			seen_vals.add(x)
			unseen_vals.remove(x)
		else:
			unseen_vals.add(x)
	return unseen_vals[0] if unseen_vals else None

How this works is that any values we know (empirically) are repeated are made accesible to allow skipping and keep track of invalid values. If the value we look at has been seen before, it will be either in the repeated vals or the list of vals only seen once, in either case, it will be skipped. What is left after the whole process is finished is a set of values only seen once, just take the first one.

runs through the whole string once, so it runs in O(n) time, and the space usage is at most twice the size of the string, so, O(n) space.

char findFirstUniqueCharacter(const string &s)
{
	unordered_set<char> st; map<int, char> index; map<char, int> rank;

	int cnt = 0;

	for (char c : s)
	{
		if (st.count(c) > 0)
		{
			if (rank.count(c) > 0)
			{
				int i = rank[c]; rank.erase(c); index.erase(i);
			}
		}
		else
		{
			st.insert(c); rank[c] = ++cnt; index[cnt] = c;
		}
	}

	return index.begin()->second;
}

public static void main (String[] args) throws java.lang.Exception
	{
		// your code goes here
		Set s1 = new HashSet();
		
		String testStr = "this is";
		for(int c = 0 ; c< testStr.length(); c++) {
			if (!s1.add(testStr.charAt(c))){
				System.out.println(testStr.charAt(c));
				break;
			}
		}
			
	}

public static void main (String[] args) throws java.lang.Exception
	{
		// your code goes here
		Set s1 = new HashSet();
		
		String testStr = "this is";
		for(int c = 0 ; c< testStr.length(); c++) {
			if (!s1.add(testStr.charAt(c))){
				System.out.println(testStr.charAt(c));
				break;
			}
		}
			
	}

public static void main (String[] args) throws java.lang.Exception
	{
		// your code goes here
		Set s1 = new HashSet();
		
		String testStr = "this is";
		for(int c = 0 ; c< testStr.length(); c++) {
			if (!s1.add(testStr.charAt(c))){
				System.out.println(testStr.charAt(c));
				break;
			}
		}
			
	}

use a linkedhashmap instead of hashset and hashmap.. it maintains order of insertion. the first one which has a value greater than 1 is the first repeated character.
Complexity: iterate over the String (n) + iterate over the map (n) = 2n = O(n)

The problem can be solved using two hashmaps in c++
map double<char,ind>;
map single<char,ind>;

traverse the array and check for each index
1)if the element is in map double then continue to next iteration
2)if the element is in map single then add the element to map double and delete it from map single
3)if the element is not in map single add it to map single with it's index value

Then finally display the character with min index in map single.

How about traversing the string in a reverse order?
Have a variable, result which will get modified when the character is encountered for the first time. The number of occurrences of characters can be stored in a hash table.

My python Solution

def FirstNonRepeatingChar(string):
    array = [0]*26

    for char in string:
        intValue = ord(char) - 97

        if array[intValue] == 0:
            array[intValue] = 1
        elif array[intValue]==1:
            array[intValue] = 2 
        else:
            continue

    for index in range(26):
        if array[index] == 1:
            print chr(index+97)
            return 

FirstNonRepeatingChar('asdfadksl')
#space complexity = O(c)
#time complexity = O(n)

here's one solution using HashMap in java :

import java.util.*;
import java.io.*;

public class FindNonrepeatSinglePass {
    static String inputstr = "aabcadeadfa";
    public static void main(String[] args) {
        HashMap<Character, Integer> mapCharacters = new HashMap<Character, Integer>();
        for(int i=0;i<inputstr.length(); i++) {
            char c = inputstr.charAt(i);
            if(mapCharacters.containsKey(c)) {
                int cnt = mapCharacters.get(c);
                mapCharacters.put(c, ++cnt);
            }
            else {
                mapCharacters.put(c, 1);
            }
        }
        Iterator<Map.Entry<Character, Integer>> iter = mapCharacters.entrySet().iterator();
        while(iter.hasNext()) {
            Map.Entry<Character, Integer> entry = iter.next();
            if(entry.getValue()>1) {
                iter.remove();
            }
        }
        System.out.println(mapCharacters.keySet().toArray()[0]);
    }

}

import java.util.*;
import java.io.*;

public class FindNonrepeatSinglePass {
    static String inputstr = "aabcadeadfa";
    public static void main(String[] args) {
        HashMap<Character, Integer> mapCharacters = new HashMap<Character, Integer>();
        for(int i=0;i<inputstr.length(); i++) {
            char c = inputstr.charAt(i);
            if(mapCharacters.containsKey(c)) {
                int cnt = mapCharacters.get(c);
                mapCharacters.put(c, ++cnt);
            }
            else {
                mapCharacters.put(c, 1);
            }
        }
        Iterator<Map.Entry<Character, Integer>> iter = mapCharacters.entrySet().iterator();
        while(iter.hasNext()) {
            Map.Entry<Character, Integer> entry = iter.next();
            if(entry.getValue()>1) {
                iter.remove();
            }
        }
        System.out.println(mapCharacters.keySet().toArray()[0]);
    }

}

Use 2 LinkedHashSet.
First hashset - single occurance
Second hasset - move the element from first to second when second time seen in the string.
at the end, check the head of the first HashSet. That would be the answer

Python solution time complexity O(N)

def firstOccurrence(S):
    dict = {}
    Array = []
    print "First Occurrence of Char:"
    for index in range(len(S)):
        if S[index] not in dict.keys():
            dict[S[index]] = 1
            Array.append(S[index])
        else: # If multiple occurrence then set value to -1
            dict[S[index]]  = -1

    #
    for elm in Array:
        if dict[elm] != -1:
            print elm
            break
S="californiac"

firstOccurrence(S)

My Python Code

def FirstNonRepeatingChar(string):
    array = [0]*26

    for char in string:
        intValue = ord(char) - 97

        if array[intValue] == 0:
            array[intValue] = 1
        elif array[intValue]==1:
            array[intValue] = 2 
        else:
            continue

    for index in range(26):
        if array[index] == 1:
            print chr(index+97)
            return 

FirstNonRepeatingChar('asdfadksl')
#space complexity = O(c)
#time complexity = O(n)