Win a copy of Pro Spring MVC with WebFlux: Web Development in Spring Framework 5 and Spring Boot 2 this week in the Spring forum!
  • 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
  • Ron McLeod
  • Paul Clapham
  • Jeanne Boyarsky
  • Liutauras Vilda
Sheriffs:
  • Rob Spoor
  • Bear Bibeault
  • Tim Cooke
Saloon Keepers:
  • Tim Moores
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Piet Souris
Bartenders:
  • Frits Walraven
  • Himai Minh

Find unique character in an array

 
Ranch Hand
Posts: 1143
5
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I am solving a leet code problem to find unique character in an array. The problem is as follows:

Given a string, find the first non-repeating character in it and return its index. If it doesn't exist, return -1.

Examples:

s = "leetcode"
return 0.

s = "loveleetcode"
return 2.

Note: You may assume the string contains only lowercase English letters

.

Here is how I am solving it:



This takes linear time. Looking for ways to further improve this code.

 
Marshal
Posts: 72927
330
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
More about names: characterFound sounds like the name of a boolean. I would suggest you use something like index, but you can doubtless improve on that name. Try containsKey() on the Map instead of the == null test. You know there is a version of Map which retains order of its entries?
 
Sheriff
Posts: 16207
271
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Using a map is overkill, in my opinion. With the map, you have to go map out the whole string. This can be done with substring and you can terminate the loop immediately when you find the solution. Solution code will be shorter, too.
 
Saloon Keeper
Posts: 12993
281
  • 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 using 'substring' Junilu? If you mean that you want to check that the remaining substring contains another occurence of the character at the current position, that algorithm has O(n²) average case time complexity. The argument that your can terminate the loop immediately when you find the solution doesn't really hold water because in any case you must inspect every character in the string at least once, so linear time is optimal.

Using a map is correct in my opinion. It ensures that the algorithm has the optimal Ө(n) time complexity. That's Big-Theta, not Big-Oh.
 
Stephan van Hulst
Saloon Keeper
Posts: 12993
281
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Punit, sadly you forgot about some of my comments in your other topic.

  • Don't create an instance of a class if doesn't implement any interfaces nor extend any classes, and doesn't have instance fields.
  • Use the diamond operator to initialize variables of generic types.
  • Don't declare variables as specific types if a less specific type will do. Declare your map as Map.
  • Instead of using map.get() followed immediately by map.put(), use map.compute().
  • Instead of iterating through the entire map to find the smallest index, use a LinkedHashMap and return the first valid index.
  • Don't use map.get() inside a loop that iterates over the key set. Iterate over the entry set instead.
  •  
    Punit Jain
    Ranch Hand
    Posts: 1143
    5
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator

    Junilu Lacar wrote:Using a map is overkill, in my opinion. With the map, you have to go map out the whole string. This can be done with substring and you can terminate the loop immediately when you find the solution. Solution code will be shorter, too.



    Did you mean by using the indexOf()?
     
    Punit Jain
    Ranch Hand
    Posts: 1143
    5
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator

    Stephan van Hulst wrote:Punit, sadly you forgot about some of my comments in your other topic.

  • Don't create an instance of a class if doesn't implement any interfaces nor extend any classes, and doesn't have instance fields.
  • Use the diamond operator to initialize variables of generic types.
  • Don't declare variables as specific types if a less specific type will do. Declare your map as Map.
  • Instead of using map.get() followed immediately by map.put(), use map.compute().
  • Instead of iterating through the entire map to find the smallest index, use a LinkedHashMap and return the first valid index.
  • Don't use map.get() inside a loop that iterates over the key set. Iterate over the entry set instead.


  • My bad. How about the following:



    Stephan van Hulst wrote:

  • Instead of iterating through the entire map to find the smallest index, use a LinkedHashMap and return the first valid index.


  • Did you mean line# 24? If yes, I can also put a break.

    Stephan van Hulst wrote:

  • Don't use map.get() inside a loop that iterates over the key set. Iterate over the entry set instead.


  • Did you say this because if I use keyset then I have to query the map again to get() the value? However, if I am using entryset then I don't have to query the map again and can get the value directly from the entry?


     
    Stephan van Hulst
    Saloon Keeper
    Posts: 12993
    281
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator

    Punit Jain wrote:Did you mean line# 24? If yes, I can also put a break.


    The break on line 28 of your new code is not correct, unless you use a LinkedHashMap instead of a HashMap. Right now it will return a random index of a character that occurs once.

    You can get rid of the comparison between currentIndex and indexToReturn. If you use a LinkedHashMap, just return the first index that belongs to a single character.

    However, if I am using entryset then I don't have to query the map again and can get the value directly from the entry?


    Correct.

    How about the following


  • Methods that do more than just get a simple property should be written as a verb. Name your method findFirstUniqueCharacter.
  • Why is your method public? Do you need to use it outside of its package?
  • Don't return magic values like -1 if your method can't find an occurrence. Either you expect that a match can be found and you throw an exception when it doesn't, or you return OptionalInt.
  •  
    Punit Jain
    Ranch Hand
    Posts: 1143
    5
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator

    Stephan van Hulst wrote:

  • Don't return magic values like -1 if your method can't find an occurrence. Either you expect that a match can be found and you throw an exception when it doesn't, or you return OptionalInt.


  • As per the problem: 'Given a string, find the first non-repeating character in it and return its index. If it doesn't exist, return -1.' Here is the updated code;




     
    Stephan van Hulst
    Saloon Keeper
    Posts: 12993
    281
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator

    Punit Jain wrote:As per the problem: 'Given a string, find the first non-repeating character in it and return its index. If it doesn't exist, return -1.'


    The client of your method can make that translation, in this case the main method:

    Here is the updated code


    You changed the map to LinkedHashMap, but now you're not making use of the benefit it provides. This is what I meant:
     
    Do not set lab on fire. Or this tiny ad:
    Thread Boost feature
    https://coderanch.com/t/674455/Thread-Boost-feature
    reply
      Bookmark Topic Watch Topic
    • New Topic