Programming Interview Question- Unique Characters in a string - C++

Programming Intervew Question: Unique Characters in a String

Question: implement an algorithm to determine if a string has all unique characters

The idea behing this (fairly easy) question is that whenever we found that any chars is repeated at least twice we should return false. In order to do that we have to look at each char we are loloking for a solution which complexity is at least . We are free to use any support data structure. is the size of the ASCII charset.

template<uint SIZEALPHABETH = 256>
bool uniqueChars(const std::string&amp;amp;amp; str)
{
typedef uint uint;
	std::array<uint,SIZEALPHABETH>; 
                       counters = {0};
	for(uint i=0 ; i< str.size() ; i++){ uint idx= str[i]%SIZEALPHABETH;
           if(counters[idx] >=1)
			return false;
		counters[idx]++ ;
	}
	return true;
}

This solution has complexity and uses constant space in the size of the alphabeth which the string is made of. We can do slightly better using a 75% less space using a boolean counters.


template<uint SIZEALPHABETH = 256>
bool uniqueChars(const std::string&amp;amp;amp; str){

	std::array<bool,SIZEALPHABETH> counters = {false};
	for(uint i=0 ; i<str.size() ; i++){
		uint idx= str[i]%SIZEALPHABETH;
		if(counters[idx])
			return false;

		counters[idx]++ ;
	}
	return true;
}

A common variant of this question is such that is not possible to use any supporting data structure.
Possible solutions involves:

    • Brute forcing all possible pair and checking for duplicates (complexity , to be precise ) as follows:

//Don't use any additional data structure
bool uniqueCharsNoDataStructure(const std::string&amp;amp;amp; str){
	for(uint i=0 ; i<str.size()/2 +1; i++){
		for(uint j=i+1 ; j<str.size() ; j++){
			if(str[i] == str[j] )
				return false;
		}
	}
	return false;
}

or alternatively sort the string first (if we are allowed to modify it) which costs and then linearly check for duplicates.

Be the first to leave a comment. Don’t be shy.

Join the Discussion

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>