• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Faster way to calculate unique characters ina string

 
Ranch Hand
Posts: 2596
Android Firefox Browser Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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: 376
2
Eclipse IDE Firefox Browser Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
    Number of slices to send:
    Optional 'thank-you' note:
  • 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: 376
2
Eclipse IDE Firefox Browser Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
more easily would be with a loop String.charAt()

 
Marshal
Posts: 79178
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
Marshal
Posts: 79178
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
Marshal
Posts: 79178
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
Scala Python Oracle Postgres Database Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
Marshal
Posts: 79178
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
Marshal
Posts: 79178
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
Marshal
Posts: 79178
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
Python C++ Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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: 376
2
Eclipse IDE Firefox Browser Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
The 2nd loop is actually indexOf() method.
 
Campbell Ritchie
Marshal
Posts: 79178
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Agree: indexOf uses a linear search and that entails a loop.
 
Don't get me started about those stupid light bulbs.
reply
    Bookmark Topic Watch Topic
  • New Topic