Find out if a string has all unique characters

11 posts / 0 new
Last post
heartin
Find out if a string has all unique characters
  1. Write an algorithm to find out if a string has all unique characters.

    • Assumption: You cannot use additional data structures.

  • NOTE: Please mention approximate time complexity. (At least if it is in order of n or n-square etc.).
Tags: 
Was it useful?
clalam
My version

public class UniqueCharString {

      public static boolean findUniqueCharStr(String str) {

            for (int i = 0; i < str.length(); i++) {

                  if (i != str.lastIndexOf(str.charAt(i))) {

                        return false;

                  }

            }

            return true;

      }

      public static void main(String[] args) {

              System.out.println("Is input having only unique characters : " + findUniqueCharStr("abcde"));

       }

}

Was it useful?
heartin
Please mention the

Please mention the approximate time complexity for this problem. Please let me know if you need help in finding the complexity.

Was it useful?
clalam
Request to post feedback about downvote

Hi All,

Please post your thoughts for downvoting the solution given above..

Was it useful?
clalam
Time Complexity

Time Complexity:

Best Case : O(1)

Worst Case : O(n) where 'n' is length of string 

Was it useful?
heartin
What will be the time

What will be the time complexity of lastIndexOf. To find last index, you need to traverse the character array of String every time. For every element, you are calling lastIndexOf. This is approximately equivalent to a nested loop (two loops, one inside another), and hence the average complexity will be in the order of O(n square)

Library functions can be deceiving. This is why most interviewers don't allow library function. 

But this problem can be done in O(n). You may try to give an implementation for lastIndexOf that uses less complexity, or don't use any library function at all. I will give you a hint: You may make an assumption on the charcter set (e.g. ASCII) and hence the count of characters that can occur.

Please do not change the above solution, add a new one below instead, as a new comment. Also mention the complexity along with it.

Was it useful?
clalam
Thanks for the detailed explanation

Thanks for the detailed explanation.. I have modified the code little bit to make use of Set behavior since it wont allow duplicates.. Please let me know if this is fine or not..

 

import java.util.HashSet;
import java.util.Set;

public class UniqueCharString {

      public static boolean findUniqueCharStr(String str) {

            Set<Character> set = new HashSet<>();

            for (int i = 0; i < str.length(); i++) {

                 if (!set.add(str.charAt(i))) {

                        return false;

                  }

            }

            return true;

      }

      public static void main(String[] args) {

              System.out.println("Is input having only unique characters : " + findUniqueCharStr("abcde"));

              System.out.println("Is input having only unique characters : " + findUniqueCharStr("abcdea"));

       }

}

Was it useful?
heartin
Yes, this is a better

Yes, this is a better solution. Good work.

Please answer below questions (an interviever might ask these).

  1. For the solution to become O(n), your Set's add should work in O(1). Can you explain that your set will always work with O(1).

  2. Can you also try to give a solution without using any library functions, still with O(n) complexity.

Was it useful?
clalam
I am not very much familiar

I am not very much familiar in finding complexity of a statement but if you see SET internal implementation it uses hashmap which will have O(1) since it uses hashcode method to find the location instead of looping. Correct me if I am wrong...

You voted 'UP'.
Was it useful?
heartin
Complexity of HashMap is not

Complexity of HashMap is not always O(1). A hash based data structure can have a complexity ranging from O(1) to O(n), based on the hash function, which is based on the Object that is added. If every different element goes to a different bucket, it has complexity of O(1) and if everyone goes to the same bucket (complete collissions) it will havea complexity of O(n). In your case, the object in question is Character, whose hash function seems to return the value of the character, which should be unique, and hence the complexity should be theoretically O(1).

That is why I said the new solution is better. And you will get the points.

However, for reasons including, every character in question is boxed to a Character class before passing in to the Set, an interviever might ask for a solution that does not use any library function, and use only primitives. Can you give a try for that as well? 

Was it useful?
heartin
A possible solution without library functions

Every character is represented by a unique number. We can have a boolean array with indexes being the number that represents the character. Every time a character is encountered, we will check if array[characterValue] is already true (if element was founf before); else we will set it as true, and continue. If element was already found before, we can exit. 

We will need to make an assumption on the character set. For instance, if the character set is ASCII, it will have 256 characters and hence we can have an array of size 256.

As an optimization, we can check upfront if the size of string is greater than 256; if it is greater than 256, it can never have only unique characters.

Solution

 public boolean isUniqueCharString(String str)

{

  if (str.length() > 256)

    return false;

  boolean charSet = new boolean[256];

  for(int i=0; i< str.length(); i++)

  {

    int charVal = str.charAt(i);

    if(charSet[charVal])

    {

      return false;

    }

    charSet[charVal] = true;

  }

  return true;

}

 

If you can find a better solution, please post it with justification to win great attractive prices and/or points.

Was it useful?

Quick Notes Finder Tags

Activities (1) advanced java (1) agile (3) App Servers (6) archived notes (2) Arrays (1) Best Practices (12) Best Practices (Design) (3) Best Practices (Java) (7) Best Practices (Java EE) (1) BigData (3) Chars & Encodings (6) coding problems (2) Collections (15) contests (3) Core Java (All) (55) course plan (2) Database (12) Design patterns (8) dev tools (3) downloads (2) eclipse (9) Essentials (1) examples (14) Exception (1) Exceptions (4) Exercise (1) exercises (6) Getting Started (18) Groovy (2) hadoop (4) hibernate (77) hibernate interview questions (6) History (1) Hot book (5) http monitoring (2) Inheritance (4) intellij (1) java 8 notes (4) Java 9 (1) Java Concepts (7) Java Core (9) java ee exercises (1) java ee interview questions (2) Java Elements (16) Java Environment (1) Java Features (4) java interview points (4) java interview questions (4) javajee initiatives (1) javajee thoughts (3) Java Performance (6) Java Programmer 1 (11) Java Programmer 2 (7) Javascript Frameworks (1) Java SE Professional (1) JPA 1 - Module (6) JPA 1 - Modules (1) JSP (1) Legacy Java (1) linked list (3) maven (1) Multithreading (16) NFR (1) No SQL (1) Object Oriented (9) OCPJP (4) OCPWCD (1) OOAD (3) Operators (4) Overloading (2) Overriding (2) Overviews (1) policies (1) programming (1) Quartz Scheduler (1) Quizzes (17) RabbitMQ (1) references (2) restful web service (3) Searching (1) security (10) Servlets (8) Servlets and JSP (31) Site Usage Guidelines (1) Sorting (1) source code management (1) spring (4) spring boot (3) Spring Examples (1) Spring Features (1) spring jpa (1) Stack (1) Streams & IO (3) Strings (11) SW Developer Tools (2) testing (1) troubleshooting (1) user interface (1) vxml (8) web services (1) Web Technologies (1) Web Technology Books (1) youtube (1)