Thursday, 10 August 2017

How to determine if a string has all unique characters in Java?

This is one of the common string based coding problem from programming job interviews. You need to write a program to determine if a given string has all unique characters or not. For example input= "Java" then your function should return false because all characters are not unique, and if the input is "Python" then your program should return true because all characters in Python are unique. For the purpose of this problem, you can assume the given String only contains ASCII printable characters, though you should always verify that with the interviewer. You can also assume that your solution needs to case-sensitive i.e. "P" and "p" will be considered two different characters and a string containing a letter in both capital and the small case will be considered unique. You are also free to solve the problem in place of using any additional data structure.

The first solution which comes to mind to solve this problem is by using a Set data structure. A Set is an unordered collection which doesn't allow duplicates. The JDK provides several Set implementations e.g. HashSet, TreeSet or LinkedHashSet but to solve this problem we can use general purpose HashSet. The add() method is used to insert an element into Set and this method returns true if an element is successfully inserted otherwise it returns false i.e. when an element is already present in the Set.

If we go through each character of String and insert them into Set using add() method then we can find if all characters of String are unique or not. If there are any duplicate characters then add() will return false and we can stop our program returning that all characters of String are not unique.

Here is the exact algorithm to solve this problem:

1) Create a Set e.g. HashSet
2) Get all characters of String using chars()
3) loop over all characters and insert into Set one at a time
4) If add() method return false then terminate the program because not all characters are unique.
5) If all characters are successfully inserted then return true because all characters of String is unique

Program to determine if a string has all unique characters in Java


Here is a Java program to convert above algorithm into code:
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

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

  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");
    String input = sc.nextLine();

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

    sc.close();
  }

  /**
   * Returns true if all characters of given String are unique
   *
   * @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;
  }
}

Output:

Please enter a String
Java
All characters of String are not unique
Please enter a String
Python
All characters of String are unique

From the output, it's clear that our program is working fine. When the user enters "Java" it returns that all characters are not unique because "a" is repeated in "Java", but when the user enters "Python" it prints "all characters are unique" because there is no duplicate character in "Python".

That's all about how to check if given string has all unique characters. As I said, there are multiple ways to do it e.g. you can do it in place, or you can use additional data structure e.g. set or hash table to determine if a string has all unique characters. This problem is also asked as for how to check if String contains duplicates or finding the repeated characters from the string. You can use the same technique to solve those problems as well.