Determine if a string has all unique characters

October 01, 2020

Problem

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

Lets try to understand the problem first. Always clear out the doubts. Clear about the character set, is it ASCII or what. Before moving on to the solution, declare your input points. Example: you are considering only lower case alphabets.

Solution using HashSet

A very simple solution can be to use a `HashSet` and just check if you found a character or not. If not, then save it. At any point, if you found a character exists in your `HashSet`, return false.

``````public boolean isUnique(String str) {
Set<Character> set = new HashSet<>();
for (int i=0; i<str.length(); i++) {
if (set.contains(str.charAt(i))) {
return false;
}
}
return true;
}``````

Complexity

The complexity of this solution would be `O(n)`

Solution using Array

Clear out from your interviewer the size of your input set. It can be 256 cgaracters or 26 characters. For this solution, lets assume characters to be 256.

We can then take a boolean array of size 256, where each index represents a character position. On finding a character, set it to true.

``````public boolean isUnique2(String str) {
if (str.length() > 256) {
//means at least one character is coming more than once
return false;
}
boolean chars[] = new boolean[256];

for (int i=0; i<str.length(); i++) {
if (chars[str.charAt(i)]) {
return false;
}
chars[str.charAt(i)] = true;
}
//did not find any duplicate
return true;
}``````

Complexity

The complexity is also `O(n)`

Solution using a Bit Vector

For this solution, lets assume we have all lower-case letters. Hence, we have 26 characters in total.

We can take an `Integer` variable which takes `4 bytes = 32 bits`. Which can help us in representing 26 characters and will be out Bit Vector.

``````public boolean isUnique_BitVector(String str) {
if (str.length() >= 26) {
return false;
}
int bit_vector = 0;
for (int i=0; i<str.length(); i++) {
int charVal = str.charAt(i) - 'a';
int shiftedVal = 1 << charVal;

if ((bit_vector & shiftedVal) > 0) {
return false;
}
bit_vector |= shiftedVal;
}
return true;
}``````

In above solution:

• First we are finding the position of the character by doing `val - 'a'`. Example, for character: `b` we will get index=1.
• Then, we will check if there is 1 bit set already or not.
• If its not set, we will set the respective bit.

Example

``````achc

Assumming last 1 byte of bit vector (8 bits)
Initial bit vector: 0 0 0 0 0 0 0 0

For 'a': charVal=0, 1 << 0 = 1
0 0 0 0 0 0 0 0 & 1 = 0
0 0 0 0 0 0 0 0 | 1 = 0 0 0 0 0 0 0 1

For 'c': charVal=2, 1 << 2 = 1 0 0
(0 0 0 0 0 0 0 0) & (1 0 0) = 0
(0 0 0 0 0 0 0 0) | (1 0 0) = (0 0 0 0 0 1 0 0)

For 'h': charVal=7, 1 << 7 = (1 0 0 0 0 0 0)
(0 0 0 0 0 1 0 0) & (1 0 0 0 0 0 0) = 0
(0 0 0 0 0 1 0 0) | (1 0 0 0 0 0 0) = (0 1 0 0 0 1 0 0)

For 'c': charVal=2, 1 << 2 = (1 0 0)
(0 1 0 0 0 1 0 0) & (1 0 0) = 1
Found > 0, return false``````

Complexity

Its `O(n)`

Similar Posts

Selection Sort Algorithm

It is one of a simple algorithm to study for a beginner to understanding sorting…

Crawler Log Folder - minimum number of operations needed to go back to the main folder after the change folder operations.

Problem The Leetcode file system keeps a log each time some user performs a…

Container with Most Water - Leet Code Solution

Problem Statement Given n non-negative integers a1, a2, …, an , where each…

Insertion Sort Algorithm

Its a kind of incremental insertion technique, where the algorithm build up…

Find the maximum sum of any continuous subarray of size K

Introduction You are given an array of integers with size N, and a number K…

Remove Duplicates from Sorted Array - Leet Code Solution

Problem Statement Given a sorted array nums, remove the duplicates in-place such…

Latest Posts

Django Python - How to Build Docker Image and Run Web-service on Apache with Python 3.9

Introduction So you have a Django project, and want to run it using docker image…

Python - How to Maintain Quality Build Process Using Pylint and Unittest Coverage With Minimum Threshold Values

Introduction It is very important to introduce few process so that your code and…

Example Jenkin Groovy Pipeline Script for Building Python Projects with Git Events and Push to Artifactory

Introduction In this post, we will see a sample Jenkin Pipeline Groovy script…

Python - How to Implement Timed-Function which gets Timeout After Specified Max Timeout Value

Introduction We often require to execute in timed manner, i.e. to specify a max…

Kubernetes - How to Set Namespace So You Do Not Need to Mention it Again and Again in Kubectl Commands.

Introduction In some of the cases, we need to specify namespace name along with…

Kubernetes - How to Configure Docker Repository to Pull Image and Configure Secret

Introduction In most of cases, you are not pulling images from docker hub public…