# [Challenge] Unique Characters in a String

#246

``````function swap(arr, i, j) {
var temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}

function partition(arr, pivot, left, right) {
var pivotValue = arr[pivot],
partitionIndex = left;

for (var i = left; i < right; i++) {
if (arr[i] == pivotValue) {
return -1;
}
if (arr[i] < pivotValue) {
swap(arr, i, partitionIndex);
partitionIndex++;
}
}
swap(arr, right, partitionIndex);
return partitionIndex;
}

function quickSort(arr, left, right, found) {
var len = arr.length,
pivot,
partitionIndex;

if (left < right) {
pivot = right;
partitionIndex = partition(arr, pivot, left, right);
if (partitionIndex == -1) {
found += 1;
} else {
found += quickSort(arr, left, partitionIndex - 1, found);
found += quickSort(arr, partitionIndex + 1, right, found);
}
}
return found
}

function check(str) {
if (quickSort(str.split(''), 0, str.length, 0) > 0) {
return 'duplicates found';
} else {
return 'all unique';
}
}``````

This implementation use the quick sort algorithm. The magic happens in the partition function.
Each time the letter at the pivot position is the same as the one at the position i, then we return -1.

In the quicksort function, if the returned pivot has a value of -1, then we increment the value > found.
at the end. we check if the value found is greater than 0. If it is the case, than it means that we have a duplicate.

#247

Well heres how I did it, In Java.

A quick loop through the characters checking for the first and last index found, if they are different then there is more than one. Breaking the loop.
Ignoring the space char.

``````     void checkDuplicates(String str) {
boolean result = false;
for (char c : str.toCharArray()) {
if (c != ' ' && str.indexOf(c) != str.lastIndexOf(c)) {
result = true;
break;
}

}
if (result) {
System.out.println("Duplicates found");
} else {
System.out.println("All unique");
}

}``````

#248

My first intuition to get a working solution, a simple nested loop that compares each element to each other element.
Pros: very straightforward logic, does not require another data structure because all comparisons are done "in-place", i.e. O(1) space complexity
Cons: O(n^2) time complexity

``````def is_unique_1(string):

for i in range(0, len(string)):               # O(n) time
for j in range(i+1, len(string)):        # O(n) time
if (string[i] ==  string[j]):
print "duplicates found."; return

print "all unique."; return``````

The most elegant (in my opinion) and tied for most efficient possible solution. This simply uses python's set data structure to eliminate all duplicate characters, and then compares the length of the set of unique characters to the length of the original string.
Pros: O(n) time complexity, takes advantage of python's built in functions (which I will always trust to be more efficient than my own implementations), short and sweet
Cons: O(n) space complexity, requires use of another data structure

``````def is_unique_2(string):

if (len(string) == len(set(string))):     # set construction takes O(n) time and takes O(n) space
print "all unique."; return

print "duplicates found."; return``````

And just for fun... an implementation that uses mergesort to first sort the string based on each char's unicode value, and then checks for any consecutive elements. While it does not use any data structures other than strings, the recursive call stack does take up O(n) space, and the time complexity is O(nlogn), so better than the nested loop, but still not as fast as creating a set.

``````def is_unique_3(string):

sorted_string = mergesort(string)    # O(nlogn) time and O(n) space

for i in range(0, len(sorted_string)-1):   # O(n) time
if (sorted_string[i] == sorted_string[i+1]):
print "duplicates found."; return

print "all unique."; return

def mergesort(string):
""" Returns a sorted str objected, with chars sorted according to unicode values
uses mergesort algorithm
time complexity: O(nlogn)
space complexity: O(n)

preconidtion: string must be python object of type str.         """

if (len(string) < 2):
return string

mid = len(string)/2

half_1 = mergesort(string[0:mid])

half_2 = mergesort(string[mid:])

return merge(half_1, half_2)

def merge(half_1, half_2):
""" Combine two sorted str objects, half_1 and half_2, into a single sorted str object and return the result.
(str sorted according to char unicode values)

precondition: half_1 and half_2 are str objects sorted according to unicode values
"""
merged = ''

while (half_1 or half_2):
if not half_1:
merged = merged + half_2[0]
half_2 = half_2[1:]
elif not half_2:
merged = merged + half_1[0]
half_1 = half_1[1:]
else:
if (ord(half_1[0]) < ord(half_2[0])):
merged = merged + half_1[0]
half_1 = half_1[1:]
else:
merged = merged + half_2[0]
half_2 = half_2[1:]

return merged``````

#249

The basic idea of my implementation is to sort the input string and then do a single scan over the string to detect duplicates. The sort will place any duplicates next to each other so the scan just needs to compare the first character of the sorted string to the second, the second to the third until it encounters a duplicate or reaches the end of the string.

Here is the code for my implementation:

``````def ischunique(input_str):
"""Determines if any given string has all unique characters (i.e. no
character in the string is duplicated). If the string has all unique
characters, print 'all unique'. If the string does not have all unique
characters, print 'duplicates found.'
"""
sorted_input = sorted(input_str)
message = "all unique"
if sorted_input:
cc = sorted_input[0]
for nc in sorted_input[1::]:
if cc == nc:
message = "duplicates found"
break
else:
cc = nc
print(message)``````

Not suggesting it should, but the mini spec provided does not include guidance that we'd expect in a "real world" spec. For example, it doesn't define what to do when the function is passed an empty string (my implementation prints "all unique") or when a non-string is passed (mine generates a type error). My implementation assumes case sensitivity. So, 'Eel' is "all unique" while 'eel' is "dupiicates found".

I also decided to name my function in a manner similar to Python's string functions (i.e. no underscores between words) even though PEP8's guidance is "to separate by underscores as necessary to improve readability."

Thanks so much for the fun exercise! It was worthwhile for me.

#250

Thanks for the feedback @benjlis! We are giving a little bit more guidance, as you suggest, in our latest challenge.

#251

The first solution I made involved using a dictionary, getting all the items in a dict and then just ask if the current char was a key on the dictionary. It worked, but the instructions said to try not to use an additional structure so I programmed another solution. Basically every character on the string is compared against the rest of the string, if the character is contained on the substring, then the message "duplicates found" is shown and the program exits. By using sys.exit, we don't have to traverse the full string, thus making the solution more efficient compared to solutions that fully parse the string even when a duplicate has been found.

``````import sys

string = "12343"
for i in range(0, len(string)):
if string[i] in string[i+1:]:
print "duplicates found"
sys.exit(1)
print "no duplicates"``````

#252

This is javascript
I am replacing characters one by one and checking if there still is same character present in the rest of the string. If so, I am increasing "var dub" by one. Finally checking if dub is more than 0.

``````function IsDouplicate() {
var string = "the text string of my choice";
var result;
var dub = 0;

for (i = 1; i < string.length; i++) {

var bokstav = string.substring(i);
var check = string.replace(bokstav,"_");

var koll = check.indexOf(bokstav);
if(koll > 0){
dub++;
}

}

if(dub > 0){
result = "Not unique";
}
else{
result = "Unique";
}

return(result);
};``````

#253

Wow, thank you all for so many contributions to this challenge! Given how popular this series is becoming, we decided to issue a new challenge every week, so check back in every Wednesday for more!

On to “winners,” with special thanks to our crack team of @moderateurs (especially @factoradic)!

We got a lot of `O(n^2)` solutions, and while it’s true that these solutions don’t use any additional data structures it would be quite unfair to reward them, as they are slow.

The hypothetical interviewer’s request that we cut out any additional data structures (for the intermediate difficulty challenge) can admittedly be confusing, especially when we consider high-level languages with a lot of C / C++ bindings. For the sake of this challenge, we should assume that implementations of sorting methods should be in-place.

There were so many great solutions, but are our favorites:

##The Winner

@marek4’s solution had a very good use of an associative array. It would be preferable if a function like this returned a boolean (even though this was explicitly not requested by the interviewer) but still, it is a very good idea especially when we know that there is a limited pool of possible values (the alphabet). His solution is as follows:

``````const findRepeat = str => {
let chars = {};

for(let c of str.split('')) {
if(chars[c]) return 'duplicates found'
chars[c] = true;
}

return 'all unique';
}

console.log('==============')
console.log(findRepeat('some random string'));
console.log(findRepeat('abcdefghijklmnopqrstuvwxyz'));
console.log(findRepeat('12345'));
console.log(findRepeat('00'));
console.log(findRepeat('fsa'));
console.log(findRepeat('fdsa'));
console.log(findRepeat('ffff'));
console.log(findRepeat('fadsfasfasdf'));
console.log('==============')
``````

His explanation:

I made a function that took in the string. Then I created an empty object chars. Then I looped through the split chars and if the char key existed in the object then I would return duplicates found. If it goes all the way through the loop then I return all unique. The rest is just testing it on a bunch of random strings

##Runner-Ups:

@jsomerstone’s solution was also very good. We like that this returns boolean, and is well-written code. Sorting is a very good idea when we deal with an array of integers, but with strings, it might be inefficient. Let’s say that we have a very long string (more than `100 000` characters), it’s obvious that it includes some duplicates, but sorting will take a lot of time.

@jonasuj’s solution had a very good use of the set but has the same problem as in @jsomerstone’s submission. Might be slow in case of very long strings

###Honorable mentions:

@buonuomo, we liked your use of a lambda map!

@betamaster97156: we were not expecting a bash solution - nice work!

Thank you everyone for taking part, we wish we could provide feedback to all of you! Hope you enjoy this week’s challenge to build an anagram detector.

#254

My take on [Challenge] Unique Characters in a String.

Would greatly appreciate feedback.

https://repl.it/H9Tb

#256

My two solutions below using JavaScript.

Solution 1
I initially thought that I would first convert the string to lower case and remove white-space using a regular expression, then convert it to an array, sort it numerically/alphabetically and then iterate over it to see if there are two consecutive characters that match each other (if so, then the string contains duplicates). I started the iteration at index 1 since the character at index 0 would have no previous character in the sequence to compare against.

``````function testUnique(str) {
str = str.replace(/\s/gi, '').toLowerCase();
var arr = str.split('').sort();
for (var i = 1; i < arr.length; i++) {
if (arr[i] === arr[i - 1]) {
return "duplicates found";
}
}
return "all unique";
}``````

Solution 2
I wanted to find a solution using regular expressions so that I didn't have to create a new array from the string. I therefore created a function to iterate over each character in the string, and if the character is not white-space then see if the number of matches for that character in the string - using the .match() method with a regex for each non-white-space character (global, and case insensitive) - is more than 1 (if so, then there are duplicates).

``````function testUnique(str) {
for (var i in str) {
var char = "[" + str[i] + "]";
if ((/\S/).test(str[i]) && str.match(new RegExp(char, "gi")).length > 1) {
return "duplicates found";
}
}
return "all unique";
}``````

#257

I know I'm super-late to this party, but here is my powershell version...

``````Function UniqueChars ([String] \$st) {
if (((\$st.ToCharArray() | Group-Object -NoElement | Sort-Object Count -Descending))[0].Count -gt 1) {"duplicates found"} else {"all unique"};
}

# Testing
\$strings = ("Hello World", "unique", "abcdefghijklmnopqrstuvwxyz1234567890-+","Developer Challenge", "test4","tes_5");
Foreach (\$str in \$strings) {
UniqueChars \$str;
}``````

1 - Take the String and break it up into a character array.
2 - Like SQL, Group and Sort the query. Group the character objects and sort them in descending order so the count of the greatest number of characters comes first.
3 - In Powershell, the object returned from the Grouping function is Microsoft.Powershell.Commands.GroupInfoNoElement which is essentially a dictionary (array of key/value pairs) with a Key (aka Count) and a value. The key/count is the number of times the letter was in the string, and the value is the letter itself. Since we already sorted this array by count, we just want the first index of the array, [0].
4 - With the indexed value into the array of group and sorted characters, we select the count and put it in a conditional (if greater than 1).
5 - There is no ternary operation that I know of in Powershell, so I just used a regular if statement to encapsulate everything in one line and could be broken out if necessary for readability.
* Testing - Create an array of strings and for each string, call the function and pass it in.

#258

Solution 1:
Casting the string to a set will remove any duplicates, so by comparing the length of the set vs the length of the original string will reveal whether there are any duplicate characters. Using the boolean value from comparing the two lengths as an index for the tuple is a neat little trick that I read about recently.

``````def compare(s):
print(("Not Unique", "All Unique")[len(set(s)) == len(s)])
compare("Subnautica ")``````

Solution 2:
The string classes built in count function returns the number of times a character is present in a string, so by iterating over the string and checking whether the count function returns a value greater than one will tell if all the characters are unique.

``````def compare(s):
for letter in s:
if s.count(letter) > 1:
print("Not Unique")
return
print("All Unique")

compare("Markiplier")``````

#259

My initial intuitive thought was to use an arraylist to add the chars and check if any of the current being added char was already there:

``````public boolean isUnique(String str) {
ArrayList<Character> ocurrences = new ArrayList<Character>();
for (Character letter : str.toCharArray()) {
if (ocurrences.contains(letter)) return false;
ocurrences.add(letter);
}
return true;
}``````

Then I proceeded to the Extra Credit and realized all the work could be done directly on the string, going through it and using the "indexOf(int ch, int fromIndex)" on each char, passing the parameter "fromIndex" as the "current index + 1":

``````public boolean optimizedIsUnique(String str) {
for (int i = 0; i < str.length()-1; i++) {
if (str.indexOf(str.charAt(i), i+1) != -1) return false;
}
return true;
}``````

#260

I used perl regular expressions to solve this. The logic goes as follows -

• sort the characters in the string (not very efficient for very long strings)
• use regular expression to keep only one copy of the character in case characters are repeated in the sorted string. The entire regular expression translates to - "Any character followed by the same character one or more time is to be substituted by that character."
• (.) - Matches any one character and create a group of that character for later use.
• \1 - Is backreference and refers to the previously selected character.
• + - Plus sign in regular expression means one or more time.
• Compare the length of the processed string with the original string and print results

``````sub hasAllUniqueChars {
my (\$chars) = @_;

# sort the string (not very efficient for long strings
my \$processedChars = join('', sort(split //, \$chars));

# Only keep the unique characters
\$processedChars =~ s/(.)\1+/\$1/g;

if (length(\$processedChars) == length(\$chars)) {
print "All Unique","\n";
return 0;
} else {
print "Duplicates found", "\n";
return 1;
}

}``````

#261

Python 3. I created a general function that utilizes set() in Python. Returns true if there are duplicates, false if not. Not sure how efficient it is, but maybe it avoids the n^2 solution of just comparing each character to the whole string.
https://repl.it/IUpT/4

#262

This is my first time posting I know I'm late to the game on this one but thought it was fun. I work in Python, C# and SQL, mostly self taught and kind of have spill over in my Python code from each of these.

My first thought was to loop through the string storing each character with its count in a dictionary, printing when a duplicate was found. However, I remembered the benefit of using sets and list in Python and came up with this first solution comparing the length of the list of characters vs. the length of unique characters in a set (by definition a set can will only have unique values in it).

I thought of checking the string to make sure it had valid characters but kept it simple by converting every character to lower case and removing white spaces. Here was my first solution

``````def char_duplicates(string):
''' Function identifies if string contains duplicate or all unique characters'''
clean_string = string.lower().replace(" ","")
string_char_list = [c for c in clean_string]
string_char_set = {c for c in clean_string}
if len(string_char_list) == len(string_char_set):
print 'all unique'
else:
print 'duplicates found'``````

After looking over other post I have seen how this could be done with less code and utilizing the 'list()' and 'set()' methods instead of comprehensions stored in variables.

I then attempted to tackle the challenge without using the list and set structures. Here is my result for that:

``````def char_duplicates(string):
'''Function identifies if string contains duplicate or all unique characters'''
dups = False
clean_string = string.lower().replace(" ", "")
for c in clean_string:
char_count = clean_string.count(c)
if char_count > 1:
print 'duplicates found'
dups = True
break
if not dups:
print 'all unique'``````

I used the string.count() method while looping through each character to get a count of each character in the string. If the count is ever greater than 1 (indicating duplicates) I break from the loop immediately without evaluating the rest of the characters in the string. If it goes through the entire string without finding a duplicate the 'dups' bool is never set the 'True' thus printing that the sting contains unique character.

Probably more efficient ways to look at doing this for a later time.

#263

function checkUnique(letters){

var haystack = "";

//loop through the input string one character at a time
for(var i = 0; i < letters.length; i++) {

``````//check whether the letter is in our collection
if (haystack.includes(letters[i])){
return "Duplicate found '" + letters[i] + "' in " + letters;
}

//add this letter to our collection
str = str + letters[i];``````

}

//we got here because there were no duplicates
return "no duplicates found";

}

#264

Java Implementation:

I am using a set to store a letter as the key. When the key is present, we know that there is a duplicate.

``````public static void hasDuplicates(String str) {
Set<String> stringSet = new HashSet<String>();
for (String string : str.split("")) {
if (stringSet.contains(string)) {
System.out.println("Duplicates Found");
break;
} else {
stringSet.add(string);
}
}
}
``````

#266

Newbie JavaScript:

My approach is to sort the characters and then check if one of them is the same as the next one. When one of the values is the same as the next, it will return ‘duplicates found.’.

I am passing all characters to lower case because there might be capital letters. The sort method for arrays considers the ascii value of characters, and cap letters ascii values are lower than lower case ascii values, so this would mess up the sorting.

Then, I’m splitting into an array to be able to `.sort` and then joining them back to trim away the spaces.

``````const findDuplicate = (str) => {
const chars = str.toLowerCase()
.split('')
.sort()
.join('')
.trim('');

for (let i = 0; i < chars.length; i++) {
if ( chars[i] === chars[i + 1]) {
return console.log('duplicate found');
}
}
return console.log('Unique');
}

``````

#267

Way late, but decided to post anyways. Solution in lua.

``````function d(s)
for b in s:gmatch(".") do
local _,p = s:gsub(b,b)
if p>1 then return "Dup found "..b end
end
end
print(d("Hello!"))
``````