CODEWITHSUNDEEP
javastringalgorithmcharunique
user21
user21

Reputation: 1351

determine if string has unique characters

The problem asks to "implement an algorithm to determine if a string has all unique character.

I saw the solution, but don't quite understand.

public boolean isUniqueChars(String str) {
    if (str.length() > 256) return false;
    boolean[] char_set = new boolean[256];
    for (int i = 0; i < str.length(); i++) {
        int val = str.charAt(i);
        if (char_set[val])
            return false;
        char_set[val] = true;
    }
    return true;
}

Do we not use parseInt or (int) converter in front of the code? (Will str.charAt[i] be automatically changed to int?) What does boolean[] char set=new boolean[256] mean? Why do we need to set char_set[val]=true?

Upvotes: 3

Views: 12045

Answers (11)

Faisal Hassan
Faisal Hassan

Reputation: 620

In JS,

const isStringUnique = str => {
      if(str){
          let obj = {}
          for(let char of str){
              obj[char] ? obj[char]++ : obj[char]=1;
          }
          
          for(let char of str){
              if(obj[char] > 1)
                return false;
          }
           return true;
          }
   return true;    
}

Upvotes: 1

Andreas
Andreas

Reputation: 159086

For best performance, you should use a Set, and add the characters of the string to the set. If the set.add(...) method returns false, it means that the given character has been seen before, so you return false, otherwise you return true after adding all the characters.

For the simple solution, use Set<Character>:

public static boolean allUniqueCharacters(String input) {
    Set<Character> unique = new HashSet<>();
    for (int i = 0; i < input.length(); i++)
        if (! unique.add(input.charAt(i)))
            return false;
    return true;
}

That will however not handle Unicode characters outside the BMP, like Emojis, so we might want to change the set to use Unicode Code Points:

public static boolean allUniqueCodePoints(String input) {
    Set<Integer> unique = new HashSet<>();
    return input.codePoints().noneMatch(cp -> ! unique.add(cp));
}

However, even Code Points do not represent "characters" as we humans think of them. For that we need to process Grapheme Clusters:

public static boolean allUniqueClusters(String input) {
    BreakIterator breakIterator = BreakIterator.getCharacterInstance(Locale.US);
    breakIterator.setText(input);
    Set<String> unique = new HashSet<>();
    for (int start = 0, end; (end = breakIterator.next()) != BreakIterator.DONE; start = end)
        if (! unique.add(input.substring(start, end)))
            return false;
    return true;
}

Or with Java 9+:

public static boolean allUniqueClusters(String input) {
    Set<String> unique = new HashSet<>();
    return Pattern.compile("\\X").matcher(input).results()
                  .noneMatch(m -> ! unique.add(m.group()));
}

Upvotes: 1

Arvind Kumar Avinash
Arvind Kumar Avinash

Reputation: 78965

Java SE 9

You can simply match the length of the string with the count of distinct elements. In order to get the IntStream of all characters, you can use String#chars on which you can apply Stream#distinct to get the Stream of unique elements. Make sure to convert the string to a single case (upper/lower) otherwise the function, Stream#distinct will fail to count the same character in different cases (e.g. I and i) as one.

Demo:

import java.util.stream.Stream;

public class Main {
    public static void main(String[] args) {
        // Test
        Stream.of(
                    "Hello", 
                    "Hi", 
                    "Bye", 
                    "India"
                ).forEach(s -> System.out.println(s + " => " + hasUniqueChars(s)));
    }

    static boolean hasUniqueChars(String str) {
        return str.toLowerCase().chars().distinct().count() == str.length();
    }
}

Output:

Hello => false
Hi => true
Bye => true
India => false

Java SE 8

static boolean hasUniqueChars(String str) {
    return Arrays.stream(str.toLowerCase().split("")).distinct().count() == str.length();
}

Upvotes: 1

Smitha
Smitha

Reputation: 575

public class UniqueString {

public static void main(String[] args) {

    String input = "tes";
    Map<String, Integer> map = new HashMap<String, Integer>();

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

        if (!map.containsKey(Character.toString(input.charAt(i)))) {
            map.put(Character.toString(input.charAt(i)), 1);
        } else {            
            System.out.println("String has duplicate char");
            break;
        }
    }   
}

}

Upvotes: 1

Tasneem
Tasneem

Reputation: 803

One way you can do is via bits.

Time Complexity : O(N) (You could also argue the time complexity is 0(1), since the for loop will never iterate through more than 128 characters.)
Space Complexity : O(1)

Consider each char as bit(whether its there or not). Example, we need to check if all the chars are unique in "abcada", so if we will check if the bit for a char is already turned on, if yes then we return false otherwise set the bit there.

Now how we do it ? All the chars can be represented as numbers and then bits. We are gonna use "set bit" and "get bit" approach.

We will assume, in the below code, that the string only uses the lowercase letters a through z.

public static boolean isUniqueChars(String str) {
    int mask = 0;
    for (int i = 0; i < str.length(); ++i) {
        int val = str.charAt(i) - 'a'; // you will get value as 0, 1, 2.. consider these as the positions inside your mask which you need to check if the bit is set or not
        if ((mask & (1 << val)) > 0) return false; // Check if the bit is already set
        mask |= (1 << val); // Set bit
    }
    return true;
}

To understand bit manipulation , you can refer

https://www.hackerearth.com/practice/notes/bit-manipulation/

https://snook.ca/archives/javascript/creative-use-bitwise-operators

It took me a while to understand bits but once I did, it was eye opening. You can solve so many problems using bits and provides most optimal solutions.

Upvotes: 3

MayurSatpute
MayurSatpute

Reputation: 35

public class CheckStringUniqueChars {

    public static boolean checkUnique(String str) {
        int i=0,j=str.length()-1;
        while(i<j) {
            if(str.charAt(i) == str.charAt(j)) {
                return false;
            }
            i++;
            j--;
        }
        return true;
    }
}

Upvotes: -2

BlueStory
BlueStory

Reputation: 265

You could see the detailed explanation in my blogpost here: Check if string has all unique characters

The simplest solution is to make a loop through all characters, use hashMap and to put each character into the hashmap table, and before this check if the character is already there. If the character is already there, it's not unique.

Upvotes: 1

Nestor Milyaev
Nestor Milyaev

Reputation: 6595

A simple solution would be to convert String to a Set and compare the lengths of corresponding objects. Use java 8:

private static boolean checkUniqueChars(String copy) {
    if(copy.length() <= 1) return true;
    Set<Character> set = copy.chars()
       .mapToObj(e->(char)e).collect(Collectors.toSet());
    if (set.size() < copy.length()){
        return false;
    }
    return true;
}

Upvotes: 2

roli agrawal
roli agrawal

Reputation: 91

We can also use HashSet Data structure to determine if string has all unique characters in java.

Set testSet = new HashSet();

for (int i = 0; i < str.length(); i++) {
    testSet.add(new Character(str.charAt(i)));
}

if (testSet.size() == str.length()) {
    System.out.println("All charcaters are Unique");
} else {
    System.out.println("All charcaters are niot unique");
}

Upvotes: 9

Richard
Richard

Reputation: 61239

Think about how you would do this with a paper and pencil.

Write out the alphabet once.

Then go through your string character by character.

When you reach a character cross it out of your alphabet.

If you go to cross out a character and find that it has already been crossed out, then you know the character appeared previously in your string and you can then stop.

That's essentially what the code you posted does, using an array. The operation completes in O(N) time with O(K) extra space (where K is the number of keys you have).

If your input had a large number of elements or you could not know what they were ahead of time, you could use a hash table to keep track of which elements have already been seen. This again takes O(N) time with O(cK) extra space, where K is the number of keys and c is some value greater than 1.

But hash tables can take up quite a bit of space. There's another way to do this. Sort your array, which will take O(N log N) time but which requires no extra space. Then walk through the array checking to see if any two neighbouring characters are the same. If so, you have a duplicate.

Upvotes: 2

Omri Aharon
Omri Aharon

Reputation: 17064

See my explanation in the comments, since you only tagged algorithm I'm assuming no language and just address the algorithm itself:

public boolean isUniqueChars(String str){

   //more than 256 chars means at least one is not unique
   //please see first comment by @Domagoj as to why 256 length
    if(str.length()>256) return false;  

        //keeping an array to see which chars have been used
        boolean[] char_set = new boolean[256];

        //iterating over the string
        for(int i=0; i<str,length;i++){

            //not sure what language this is, but let's say it returns an
            //int representation of the char
            int val=str.charAt(i);

            //meaning this has been set to true before, so this char is not unique
            if(char_set[val]) 
                //nope, not unique
                return false;

            //remember this char for next time
            char_set[val]=true;
        } 

    //if we reached here, then string is unique
    return true;
}

Upvotes: 5

Related Questions