first_none_repetable_character.cpp

#include "stdafx.h"

#include <list>
#include <bitset>
#include <array>
#include <vector>
using namespace std;

// LOL what where I thinking
// Going to fancy trying to avoid inner loop O(N^2) and even hash function
char first_none_repetable_character(const std::string &str)
{
	list<char> l;
	list<char>::iterator itrs[CHAR_MAX + 1];
	bool existing_chars[CHAR_MAX + 1] = { 0 };
	bool repeted_chars[CHAR_MAX + 1] = { 0 };
	char current_none_repeted = str[0];

	for (int i = 0; i < str.size(); ++i)
	{
		char char_current = str[i];

		if (!existing_chars[char_current])
		{
			existing_chars[char_current] = true;
			l.push_front(char_current);
			itrs[char_current] = l.begin();
			current_none_repeted = (-unsigned char(current_none_repeted == 0)&char_current) | ((unsigned char(current_none_repeted == 0) - unsigned char(1))&current_none_repeted);
		}
		else
		{
			if (!repeted_chars[char_current])
			{
				repeted_chars[char_current] = true;
				if (char_current != current_none_repeted)
					l.erase(itrs[char_current]);
				else
				{
					l.pop_back();
					//OLD//current = (-unsigned char(l.end() != l.begin())&l.back()) | ((unsigned char(l.end() != l.begin()) - unsigned char(1))&0);
					if (l.end() != l.begin())
						current_none_repeted = l.back();
					else
						current_none_repeted = 0;
				}
				
			}			
		}
	}
	return current_none_repeted;
}


// So much better... and easier to understan 
char first_none_repetable_character2(const std::string &str)
{
	
	// no negative char in tests... but should probably use UCHAR_MAX and an offset later to handle negative char
	int char_count[CHAR_MAX + 1] = { 0 };
	for (char char_current : str)
	{
		char_count[char_current] += 1;
	}

	for (char char_current : str)
	{
		if (char_count[char_current] == 1)
			return char_current;
	}
	return 0;
}