__Implement an algorithm to determine if a string has all unique characters. With and without using extra additional data structures__/**

* Implement an algorithm to determine if a string has all unique characters.

* With and without using extra additional data structures?

*

**@author**Sonu Mishra

__*/__

**public**

**class**StringContainsUniqueCharacter {

/**

* Without using extra DS.

* Ignoring int variable. Time complexity is

* O(n), where n is the length of the string, and space complexity is O(n).

* We can reduce our space usage a little bit by using a bit vector.We will

* assume, in the below code, that the string is only lower case ‘a’ through

* ‘z’.This will allow us to use just a single int

__*__

**@param**str: String to check

**@return : true/false**

***/**

**int**checker = 0;

**for**(

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

**int**val = str.charAt(i) - 'a';

**if**((checker & (1 << val)) > 0)

**return**

**false**;

checker |= (1 << val);

}**return**

**true**;

}

/**

* Using extra variable. For simplicity, assume char set is ASCII (if not,

* we need to increase the storage size.The rest of the logic would be the

* same)

*

*

**@param**str: String to Check

**@return : true/false**

***/**

**public**

**static**

**boolean**isUniqueChars2(String str) {

**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**;

}

**public**

**static**

**void**main(String[] args) {

System.

*out*.println(

*isUniqueChars*("abcdefgh12345a678"));

System.

*out*.println(

*isUniqueChars2*("154678"));

}

}

__Alternatively, we could do the following:__
1. Check every char of the string with every other char of the string for duplicate

occurrences.This will take O(n^2) time and no space.

2. If we are allowed to destroy the input string, we could sort the string in

O(n log* n) time and then linearly check the string for neighboring characters that are

identical.Careful, though many sorting algorithms take up extra space.

identical.Careful, though many sorting algorithms take up extra space.

## 0 comments:

Post a Comment