• Post Reply Bookmark Topic Watch Topic
  • New Topic

Faster way to calculate unique characters ina string  RSS feed

 
Ranch Hand
Posts: 2596
Android Firefox Browser Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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!


 
Ranch Hand
Posts: 323
Eclipse IDE Firefox Browser Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
use a Set, as a HashSet in Java.
 
Manish Hatwalne
Ranch Hand
Posts: 2596
Android Firefox Browser Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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
Ranch Hand
Posts: 323
Eclipse IDE Firefox Browser Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
more easily would be with a loop String.charAt()

 
Sheriff
Posts: 57845
178
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Ranch Hand
Posts: 2596
Android Firefox Browser Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Sheriff
Posts: 57845
178
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Sheriff
Posts: 57845
178
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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.
 
Bartender
Posts: 2407
36
Linux Oracle Postgres Database Python Scala
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Do you have to use Java? For example, in Scala it's easy:

 
Manish Hatwalne
Ranch Hand
Posts: 2596
Android Firefox Browser Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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
Sheriff
Posts: 57845
178
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
There is a second loop in line 4 where you are seeking the index of a letter.
 
Manish Hatwalne
Ranch Hand
Posts: 2596
Android Firefox Browser Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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
Sheriff
Posts: 57845
178
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Sheriff
Posts: 57845
178
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
There is a discussion about a similar problem, only using words not letters, in another forum of ours.
 
Ranch Hand
Posts: 789
C++ Linux Python
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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
Ranch Hand
Posts: 323
Eclipse IDE Firefox Browser Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
The 2nd loop is actually indexOf() method.
 
Campbell Ritchie
Sheriff
Posts: 57845
178
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Agree: indexOf uses a linear search and that entails a loop.
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!