How to check if a String has all unique characters in Java? [Solved]

Hello guys, its been long time since I shared any interesting coding problem but the wait is over. Today, I am going to share one interesting and popular String based coding problem which you would love to solve. Today's coding challenge is to find out if a given string has all unique characters or not, for example, if given String is "Java" then your function should return false because all styles from this String are not unique. On the other hand, if the given String is "Python," then your function should return true because all characters are unique in this String. Btw, don't just jump on the solution if this is ever asked to you on Interview; instead, you should ask a couple of good questions to demonstrate your requirement gathering skill and attention for details.

For example, you can ask if the given String is ASCII or Unicode? The answer would most likely be ASCII because that makes the problem more straightforward, but once you have solved it quickly, depending upon your experience, the Interviewer can also ask you how to solve the problem if it's a Unicode String. If you know the difference between ASCII and Unicode, then you can possibly suggest some tweaks to your algorithm.

Similarly, you can also ask if your algorithm should be case-sensitive or not? e.g., if it contains 'a' and 'A' then whether your solution should consider String unique or not. In this example, we assume, the answer is case-sensitive, which means they will be treated as different characters. Remember, the ASCII code for 'a' and 'A' is different.

Another question you should ask the Interviewer is whether the additional data structure is allowed or not, e.g. whether you can use HashSet or HashMap or not. This makes your solution a lot simpler. Sometimes, you can also ask if additional memory is allowed or not because if you use an additional data structure, then obviously you need additional memory. 

If not allowed, then you have to solve the problem in place. Here we'll assume that additional data structure is allowed.

One more question, which you should ask is will the given String fits on memory or not? Yes, this is something rare but the solution to sort 100 numbers and 10GB file of number is different, so is the case here. If String is massive and it cannot be fit on memory, then you cannot determine if all characters are unique or not in one go, you need to stream the String from disk. Here once again, we assume that String can be fit in memory. 

Now let's jump into the solution part

Solution - how to find if all characters of String is Unique

If you have been doing some String based coding challenges, then you might have come across questions like how to find if String contains duplicates or not? Or how to find the first non-repeated character of String? Well, if you have solved those questions, then this won't be a difficult one. In fact, if you can prove that String contains duplicate it means, you already solve the problem, all of its characters are not unique.

There are a couple of ways to solve this problem, and we'll see three of them in this article.

1. Using HashSet

The simplest way is by using HashSet, which only allows unique values if you try to insert a duplicate one, it will return false. Since it's easy to get the character array from String in Java using char(), you can solve this problem by iterating over the character array and inserting each character in HashSet. 

As soon as you try to enter a duplicate character, the add() method of HashSet will return false, and you can prove that all characters of String are not unique.

This solution has a time complexity of O(n) because in the worst case, you need to traverse all characters, like when String is unique.

Here we are assuming that insertion on HashSet takes O(1) time, which is the best case for HashSet because it is based upon hash table data structure. The solution also needs additional memory of O(n) because in the worst case, your HashSet has to store all characters.

2. Using HashMap Lookup

If let's say Interviewer said that you cannot use HashSet just to increase the challenge for you but allows you to use HashMap. In this case, you cannot leverage the Set's property of not allowing duplicates. Instead, you need to build that logic by yourself. Sine HashSet is actually based upon HashMap; this shouldn't be difficult. 

You can follow the same steps given in the above solution like
i) get the character array from String
ii) iterate over char array
iii) check if the character exists in HashMap using the get() method if it returns true then return from the method because all characters of String are not unique.

This solution also has a time complexity of O(n) and space complexity of O(n) because in the worst case, you need to check all characters and your HashMap will also contain all characters. This solution is good only if most of the String you are receiving doesn't contain unique characters because here the worst case is when all characters of your String are unique.

So if your job is to filter input and there is a 90% chance that String will be unique, this algorithm will run 90% of the time on its worst case. Given it is still O(n), it should be preferred with any O(n^2) algorithm, though.

From an optimization perspective, you can leverage the fact that the input String will be ASCII. Since the characters are in ASCII, we could potentially use an array of size 128 (or 256 for extended ASCII) instead of HashMap and set the value of the respective index, like if you encounter 'a' then index, 65 should be set to 1.

If you see the index is already set, 1 means the character has already occurred in the String; hence all characters of String are not unique. For further optimization, you can use a boolean array instead of an int array because boolean takes 1 bit while int takes 8 bits. In the case of a boolean array, by default, each index will have the value 'false,' when you process a character, just mark it true and follow the same logic given above.

3. In-Place solution [Brute Force Solution]

Things get really challenging if Interviewer says that additional data structures are not allowed, and you cannot use HashMap, Hashtable, or another array. You have to find if String contains all unique characters in place, without using any additional memory.

Only a couple of variables are allowed. If you remember, time vs. memory tradeoff, then to save memory, we need to compromise with speed. Since an additional data structure is not allowed, which means fast lookup (1) of HashMap is no more an option, we have to compare each character with every other character to determine if it is unique not.

Here is the exact algorithm to check if all characters of String are unique in place in Java:

• get the char array from String
• scan each character by iterating over char array
• for each character, scan all other characters in an array, if there is a match then return false
• return true if you reached the end of the array without encountering a match for all characters

The space complexity of this solution is O(1) because we are not using any additional memory. The time complexity of this solution is O(n^n) because, for each character, we have to check every other character. This is obvious from the nested loop we have used in the solution. This is also the brute force solution to this problem.

Java Program to determine if String don't have duplicate characters

Here is our complete Java program to determine if the given string contains only unique characters and there are no duplicates. This program encompasses all three solutions we have discussed so far. You can copy-paste this solution and run it in your favorite IDE like Eclipse or IntelliJIDEA. 

You can also write more unit tests that will improve your coding and testing skill, I highly recommend that, and if you need a resource, check this course from Udemy. It's great to learn JUnit and Mockito, two essential testing tools for Java developers. 

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

/*
 * Java Program to check if all characters of a given String are unique. 
 */
public class StringUniqueProblem {

  public static void main(String[] args) throws Exception {

    // create Scanner to read user input
    Scanner sc = new Scanner(System.in);

    System.out.println("Please enter a String of your choice");
    String input = sc.nextLine();

    if (isUnique(input)) {
      System.out.println("All characters of String are unique");
    } else {
      System.out.println("Sorry, String contains duplicate characters");
    }

    sc.close();
  }

  /**
   * Returns true if all characters of given String are unique
   * i.e. there is no duplicate characters
   * 
   * @param input
   * @return true if no duplicate characters
   */
  public static boolean isUnique(String input) {

    // Create a Set to insert characters
    Set<Character> set = new HashSet<>();

    // get all characters form String
    char[] characters = input.toCharArray();

    for (Character c : characters) {
      if (!set.add(c)) {
        return false;
      }
    }
    return true;
  }
}

Now, let's test this program by running and entering input:

Output

Please enter a String
Python
All characters of String are unique
Please enter a String
Java
Sorry, String contains duplicate characters

You can see that our program is working as expected. It's correctly finding if String contains duplicate character or not, I mean whether String is unique or not. 

That's all about how to find if a given String contains only unique characters or not. We have seen three ways to solve the problem, like using a set, using the hash map, and in place without additional memory. You can see how choosing a suitable data structure can simplify the solution and increase performance.

Hence a good knowledge of data structure and algorithms is mandatory for any programmer. If you are interested to learn more about data structures, I suggest reading a good on DS and Algorithms, like Introduction to Algorithms by Thomas H. Cormen.

On the other hand, if you are preparing for programming/coding interviews and looking for more such problems to boost your preparation, you can check Cracking the Coding Interview book, which contains more than 189 issues from various tech interviews.

Other String based Coding Interview Problems for Practice

• How to check if two Strings are anagrams of each other? (solution)
• How to Print duplicate characters from String? (solution)
• How to program to print the first non-repeated character from String? (solution)
• How to return the highest occurred character in a String? (solution)
• How to check if a string contains only digits?  (solution)
• How to reverse words in a sentence without using a library method? (solution)
• How to count the number of vowels and consonants in a String? (solution)
• How to find all permutations of String? (solution)
• How to convert a numeric string to an int? (solution)
• 10 Algorithms Courses to Crack Programming Job Interviews (courses)
• How to count the occurrence of a given character in String? (solution)
• How to check if String is Palindrome? (solution)
• How to find duplicate characters in a String? (solution)
• How to reverse a String in place in Java? (solution)
• How to reverse String in Java using Iteration and Recursion? (solution)
• 100+ Data Structure and Algorithms Interview Questions (questions)

Thanks for reading this String coding interview question and solution so far. If you like this String interview problem then please share it with your friends and colleagues. If you have any questions or feedback then please drop a comment.

P. S. - If you want to improve your DSA and problem solving skill and looking for some Free Algorithms courses to improve your understanding of Data Structure and Algorithms, then you should also check this list of Free Data Structure and Algorithms Courses for Programmers.