The way to verify if a String has all distinctive characters in Java? [Solved]

Equally, you may as well ask in case your algorithm must be case-sensitive or not? e.g., if it incorporates ‘a’ and ‘A’ then whether or not your answer ought to take into account String distinctive or not. On this instance, we assume, the reply is case-sensitive, which implies they are going to be handled as completely different characters. Bear in mind, the ASCII code for ‘a’ and ‘A’ is completely different.

One other query you must ask the Interviewer is whether or not the further information construction is allowed or not, e.g. whether or not you should use HashSet or HashMap or not. This makes your answer lots easier. Generally, you may as well ask if further reminiscence is allowed or not as a result of in case you use an extra information construction, then clearly you want further reminiscence. 

Yet another query, which you must ask is will the given String matches on reminiscence or not? Sure, that is one thing uncommon however the answer to type 100 numbers and 10GB file of quantity is completely different, so is the case right here. If String is very large and it can’t be match on reminiscence, then you definately can’t decide if all characters are distinctive or not in a single go, you could stream the String from disk. Right here as soon as once more, we assume that String could be slot in reminiscence. 

Resolution – the right way to discover if all characters of String is Distinctive

When you’ve got been doing a little String primarily based coding challenges, then you definately might need come throughout questions like the right way to discover if String incorporates duplicates or not? Or the right way to discover the primary non-repeated character of String? Properly, when you’ve got solved these questions, then this may not be a troublesome one. In reality, in case you can show that String incorporates duplicate it means, you already remedy the issue, all of its characters will not be distinctive.

There are a few methods to unravel this drawback, and we’ll see three of them on this article.

1. Utilizing HashSet

The only means is by utilizing HashSet, which solely permits distinctive values in case you attempt to insert a replica one, it’s going to return false. Since it is simple to get the character array from String in Java utilizing char(), you may remedy this drawback by iterating over the character array and inserting every character in HashSet. 

This answer has a time complexity of O(n) as a result of within the worst case, you could traverse all characters, like when String is exclusive.

2. Utilizing HashMap Lookup

If as an instance Interviewer stated that you can’t use HashSet simply to extend the problem for you however permits you to use HashMap. On this case, you can’t leverage the Set’s property of not permitting duplicates. As an alternative, you could construct that logic by your self. Sine HashSet is definitely primarily based upon HashMap; this should not be troublesome. 

This answer additionally has a time complexity of O(n) and house complexity of O(n) as a result of within the worst case, you could verify all characters and your HashMap can even include all characters. This answer is nice provided that many of the String you’re receiving does not include distinctive characters as a result of right here the worst case is when all characters of your String are distinctive.

So in case your job is to filter enter and there’s a 90% probability that String shall be distinctive, this algorithm will run 90% of the time on its worst case. Given it’s nonetheless O(n), it must be most popular with any O(n^2) algorithm, although.

From an optimization perspective, you may leverage the truth that the enter String shall be ASCII. For the reason that characters are in ASCII, we may probably use an array of dimension 128 (or 256 for prolonged ASCII) as a substitute of HashMap and set the worth of the respective index, like in case you encounter ‘a’ then index, 65 must be set to 1.

For those who see the index is already set, 1 means the character has already occurred within the String; therefore all characters of String will not be distinctive. For additional optimization, you should use a boolean array as a substitute of an int array as a result of boolean takes 1 bit whereas int takes 8 bits. Within the case of a boolean array, by default, every index can have the worth ‘false,’ while you course of a personality, simply mark it true and observe the identical logic given above.

3. In-Place answer [Brute Force Solution]

Issues get actually difficult if Interviewer says that further information constructions will not be allowed, and you can’t use HashMap, Hashtable, or one other array. It’s a must to discover if String incorporates all distinctive characters in place, with out utilizing any further reminiscence.

Solely a few variables are allowed. For those who bear in mind, time vs. reminiscence tradeoff, then to avoid wasting reminiscence, we have to compromise with pace. Since an extra information construction is just not allowed, which means quick lookup (1) of HashMap isn’t any extra an possibility, we’ve to match every character with each different character to find out whether it is distinctive not.

Right here is the precise algorithm to verify if all characters of String are distinctive in place in Java:

• get the char array from String
• scan every character by iterating over char array
• for every character, scan all different characters in an array, if there’s a match then return false
• return true in case you reached the tip of the array with out encountering a match for all characters

The house complexity of this answer is O(1) as a result of we aren’t utilizing any further reminiscence. The time complexity of this answer is O(n^n) as a result of, for every character, we’ve to verify each different character. That is apparent from the nested loop we’ve used within the answer. That is additionally the brute power answer to this drawback.

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

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

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

    // create Scanner to learn person enter
    Scanner sc = new Scanner(System.in);

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

    if (isUnique(enter)) {
      System.out.println("All characters of String are distinctive");
    } else {
      System.out.println("Sorry, String incorporates duplicate characters");
    }

    sc.shut();
  }

  /**
   * Returns true if all characters of given String are distinctive
   * i.e. there is no such thing as a duplicate characters
   * 
   * @param enter
   * @return true if no duplicate characters
   */
  public static boolean isUnique(String enter) {

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

    // get all characters kind String
    char[] characters = enter.toCharArray();

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

Now, let’s check this program by working and getting into enter:

Output

Please enter a String
Python
All characters of String are distinctive
Please enter a String
Java
Sorry, String incorporates duplicate characters

Therefore an excellent information of information construction and algorithms is necessary for any programmer. If you’re to be taught extra about information constructions, I counsel studying an excellent on DS and Algorithms, like Introduction to Algorithms by Thomas H. Cormen.

Alternatively, if you’re getting ready for programming/coding interviews and searching for extra such issues to spice up your preparation, you may verify Cracking the Coding Interview e book, which incorporates greater than 189 points from numerous tech interviews.

• The way to verify if two Strings are anagrams of one another? (answer)
• The way to Print duplicate characters from String? (answer)
• The way to program to print the primary non-repeated character from String? (answer)
• The way to return the very best occurred character in a String? (answer)
• The way to verify if a string incorporates solely digits?  (answer)
• The way to reverse phrases in a sentence with out utilizing a library technique? (answer)
• The way to depend the variety of vowels and consonants in a String? (answer)
• The way to discover all permutations of String? (answer)
• The way to convert a numeric string to an int? (answer)
• 10 Algorithms Programs to Crack Programming Job Interviews (programs)
• The way to depend the prevalence of a given character in String? (answer)
• The way to verify if String is Palindrome? (answer)
• The way to discover duplicate characters in a String? (answer)
• The way to reverse a String in place in Java? (answer)
• The way to reverse String in Java utilizing Iteration and Recursion? (answer)
• 100+ Knowledge Construction and Algorithms Interview Questions (questions)