### Find the Median of Two Sorted Arrays - Leet Code Solution

Problem Statement There are two sorted arrays nums1 and nums2 of size m and n…

October 01, 2020

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.

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;
}
set.add(str.charAt(i));
}
return true;
}
```

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

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;
}
```

The complexity is also `O(n)`

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.

```
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
```

Its `O(n)`

Problem Statement There are two sorted arrays nums1 and nums2 of size m and n…

Problem Statement The string “PAYPALISHIRING” is written in a zigzag pattern on…

Here are some tips while giving your coding interviews. 1. Never try to jump to…

This is kind of preliminary technique of sorting. And, this is the first…

Problem Statement Given an array, rotate the array to the right by k steps…

Here are some tips while preparing for your coding interviews. 1. Do study or…

Introduction We have a page, for example a . And, upon submission we would want…

Problem Statement I have a parent component which loads some list categories…

Introduction This post is in contuation of our previous post: How to use Draft…

Introduction In this post, we will use in Next.js with strapi. And, we will…

Introduction In this post, we will integrate Next.js with Strapi fully. And we…

Introduction Next-auth is a fantastic library for abstracting handling of…