Faster way to calculate unique characters ina string

[Manish Hatwalne]

I have a a given string which may contain any number of alpha-numeric characters, I need to calculate & extract unique characters from this string. That is if the string is "aaabcbbbdaa" I should get 4 (number of unique characters) and "abcd" as those unique characters.

I have a rudimentary code with a single for loop, but I am wondering if there is a better/more efficient way of doing this. Any pointers would be highly appreciated!

            
            int uniqueChars = 0;
            String temp = "";
            for(int i=0; i < substr.length(); i++){
		if(-1 == temp.indexOf(substr.charAt(i))){
			uniqueChars++;
		}
		temp = temp + substr.charAt(i);
	   }	

[German Gonzalez-Morris]

use a Set, as a HashSet in Java.

[Manish Hatwalne]

German Gonzalez-Morris wrote:use a Set, as a HashSet in Java.

I thought about that, but how do I push string characters in a Set without loop. String.asCharArray() cannot be pushed directly!
Or am I missing something obvious?

[German Gonzalez-Morris]

more easily would be with a loop String.charAt()

[Campbell Ritchie]

You cannot get a Stream from a String but you can from the char[]; there is a method in the Arrays class which gives you an int stream; you can collect that in a set but you might have to do some casting to convert the ints to chars.

[Manish Hatwalne]

I am afraid both these approaches (char stream and with loop and String.charAt() ) may not be more efficient than what I have already written!

[Campbell Ritchie]

What do you mean by more efficient?
If you mean readable, then your original option loses hands down.
If you mean in terms of memory use, then you are creating multiple String objects and rejecting them.
If you mean in terms of execution speed, then your suggestion runs in quadratic time whereas the other suggestions would run in linear time.

[Campbell Ritchie]

Manish Hatwalne wrote: . . . how do I push string characters in a Set without loop. . . .

You can add a String or a char[], remembering that a char[] is not a String. You do have to iterate the array and add the individual chars to your set.

[chris webster]

Do you have to use Java? For example, in Scala it's easy:

val s = "aaabcbbbdaa"                           
val chars = (s.toSet).mkString                  
println(s"The string ${s} contains ${chars.size} distinct characters: ${chars}")
//Prints: The string aaabcbbbdaa contains 4 distinct characters: abcd

[Manish Hatwalne]

Campbell Ritchie wrote:What do you mean by more efficient?
If you mean readable, then your original option loses hands down.
If you mean in terms of memory use, then you are creating multiple String objects and rejecting them.
If you mean in terms of execution speed, then your suggestion runs in quadratic time whereas the other suggestions would run in linear time.

I meant efficiency in terms of time complexity. I have a single loop (linear), what part of code will make it quadratic? Am I missing something obvious?

Edit: Never mind, I got it!

[Campbell Ritchie]

There is a second loop in line 4 where you are seeking the index of a letter.

[Manish Hatwalne]

Campbell Ritchie wrote:There is a second loop in line 4 where you are seeking the index of a letter.

Yeah, I got it. That's why I edited my post and acknowledged that! :-)

[Campbell Ritchie]

I thought you had found it from the bold print at the end of your previous post, but thought I should still point it out.

[Campbell Ritchie]

There is a discussion about a similar problem, only using words not letters, in another forum of ours.

[Guillermo Ishi]

Campbell Ritchie wrote:There is a second loop in line 4 where you are seeking the index of a letter.

I don't see it?

[German Gonzalez-Morris]

The 2nd loop is actually indexOf() method.

[Campbell Ritchie]

Agree: indexOf uses a linear search and that entails a loop.