STL list problem

[Harry Potter]

I am trying to solve a problem "find if a string has all unique characters", in different ways possible.

One way i thought was, i could store the characters in a 'list', and then sort the list, and then just pop one character and compare it with the next one, if they are same, the string has duplicates. Effectively this should give nlogn time.

But, as i see it, my list is not pushing duplicate characters. If the char is duplicate, it is not pushing it in the list. Which i am not understanding why, coz list are supposed to take any values, And that is why they have 'list::unique' function too.

Please have a look at the code, and suggest if there is any problem...

#include <iostream>
#include <string>
#include <list>
#define Null 00


using namespace std;


int main(){

	string myStr = "howareyoudoing???";
	int flag = 0;
	list<char> LL;

	for(int i = 0; myStr[i+1] != '\0'; i++){
		LL.push_back(myStr[i]);
	}

	//LL.sort();

	for(list<char>::iterator iter = LL.begin(); iter != LL.end(); ){

		char temp = (*iter);
		cout << temp;
		LL.remove((*iter));
		iter = LL.begin();
		if(temp == (*iter)){
			cout << (*iter) << " is duplicated" << endl;
			break;
			flag = 1;
		}
	}

	if(!flag) cout << "All uniques!!" << endl;

	return 0;
}

[Peter87]

for(int i = 0; myStr[i+1] != '\0'; i++){
	LL.push_back(myStr[i]);
}

This will miss the last character and will probably crash if myStr is empty.

line 31 is never reached because it is after the break;

[Harry Potter]

line 31 is not the main problem. (i changed it and checked again),,

As i had checked earlier while testing itself, the list is not getting the duplicate characters. I am also printing the character at 'iter', and there you can see it is omitting the duplicate characters, i dont know why....

[3hM2Nwbp]

This should work. Exploring the Strings library would be a great boon for future tasks.

#include <string>
#include <iostream>

int main()
{
  std::string str = "ABCDEFG";
  bool unique = true;
  for(int i = 0; i < str.size(); ++i)
  {
    // If the first occurrence ( std::string::find(char) ) is not the last occurrence ( std::string::rfind(char) )
    if(str.find(str[i]) != str.rfind(str[i]))
    {
      unique = false;
      break;
    }
  }
  std::cout << "Unique? " << (unique ? "true" : "false") << std::endl;
}

[Harry Potter]

i did this... (well, similar to this)

But i specially wanted to do it using the 'list' of stl. Because i wanted to use its 'sort' function...

The algo you gave me, and the similar one that i had designed has complexity of n^2, (coz in the worst case it has to traverse n guys n times)... but with sort, it reduces to nlogn, which is quite significant...

[Peter87]

You can also sort a string using std::sort.
std::sort(myStr.begin(), myStr.end());

You can solve the problem in linear time using a lookup table but it might very well be slower than sorting for small strings.

bool allUnique(const std::string& str)
{
	bool charSeen[256] = {};
	for (std::size_t i = 0; i < str.size(); i++)
	{
		unsigned char c = str[i];
		if (charSeen[c])
		{
			return false;
		}
		charSeen[c] = true;
	}
	return true;
}

[Harry Potter]

awesome!
Thank you, <why dint i think of this??>

[Cubbi]

Since you said "different ways", how about str.size() == set<char> (str.begin(), str.end()).size()

[Harry Potter]

wow,
thats also a nice way... That too will take nlogn time.
Thank you, appreciate it.