-
Notifications
You must be signed in to change notification settings - Fork 1.2k
Expand file tree
/
Copy pathisUnique.js
More file actions
79 lines (67 loc) · 1.91 KB
/
isUnique.js
File metadata and controls
79 lines (67 loc) · 1.91 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
var allUniqueChars = function(string) {
// O(n^2) approach, no additional data structures used
// for each character, check remaining characters for duplicates
for (var i = 0; i < string.length; i++) {
for (var j = i + 1; j < string.length; j++) {
if (string[i] === string[j]) {
return false; // if match, return false
}
}
}
return true; // if no match, return true
};
const everyCharUnique = (str, indexOffset = 'a'.charCodeAt()) => {
let counterTable = Number();
for(let index of [...str].map(c => c.charCodeAt() - indexOffset)) {
const mask = 1 << index;
if(counterTable & mask)
return false;
counterTable |= mask;
}
return true;
};
function everyCharUnique(str) {
let obj = {};
for (let i = 0; i < str.length; i++) {
if (obj[str[i]] && obj[str[i]] >= 1) {
return false;
} else {
obj[str[i]] = 1;
}
}
return true;
}
/**
Sorting solution
Time O(n log n)
Space O(n) [for recursion]
We can also sort the input string as an array
Then iterate over the input string
If we find a duplicate character return false
Otherwise if we get through the entire string return true
**/
function everyCharUnique(string) {
const str = string.split('').sort()
for (let i = 1; i < str.length; i++) {
if (str[i] === str[i - 1]) {
return false
}
}
return true
}
/**
HashSet Solution
Time & Space O(n)
The Hashing function can also be reduced to two lines
Utilizing a HashSet function, we only keep track of unique elements
Then compare the length / size of both string & set respectively
**/
function everyCharUnique(string) {
const set = new Set(string.split(''))
return string.length === set.size
}
/* TESTS */
console.log(everyCharUnique('abcd'), 'true');
console.log(everyCharUnique('abccd'), 'false');
console.log(everyCharUnique('bhjjb'), 'false');
console.log(everyCharUnique('mdjq'), 'true');