[Challenge] Unique Characters in a String

challenge
#1

Code Challenge, April 19th 2017

Every two weeks, we feature the type of brain-teasing question that might be asked in a full-stack developer's job interview, similar to the FizzBuzz Challenge often used at places like Facebook and Google.

For this week's challenge:

Write a function that 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."

Scroll down and reply to this thread with your code to participate! Don't just submit your code, remember to explain your solution, too!

Don't worry if someone has already posted the solution you had in mind, this should be a fun challenge for you, so why not write it up and post it anyway, or consider doing something for extra credit?

Extra Credit

Intermediate Difficulty

If you'd like to go a step further:

Don’t use any additional data structures.

Make your submission as efficient as possible!

The Winning Entries

See our favorite submissions (and why we picked them) here.

How to participate

Though this challenge has now "ended" in the sense that we have chosen our favorites, you should feel free to post your own response! Just make sure that your code is correctly formatted.

If you do want to try this, why not stretch yourself a bit further and try this challenge in a language that you don't know well, or a language that isn't as well suited to this sort of task as the likes of Python? Or go for a solution that is off-the-wall, a very unusual (yet interesting and artful) way of solving the problem that is likely not maximally efficient? You won't necessarily stand a better chance of "winning" this way, but it will help you to push yourself if you need something more challenging.

Happy coding!

The fine print:
* Remember, the point of code challenges like these is to test and stretch yourself with an unusual problem, so don't be dissuaded if you find it difficult or don't know where to start! Start with Googling, but see if you can find out how to think about the problem and what tools you need to solve it, but don't just go looking for the solution itself. This way, it'll be a better learning exercise for you - developers can't always find and copy "the right answer" online, which is why questions like these are used in developer job interviews! Interviewers want to be able to see how you think through problems and not just whether or not you can solve them.
* Please don't use any unusual repos or anything that will make it more difficult for your fellow users or Codecademy staff to assess your answer.
* Do you have a code challenge to share with other users? Let us know! Make a new topic with [Challenge] in the title to open a challenge, maybe we'll even feature it in our next newsletter!

Essential Information on Code Challenges
#2

Here's how I read the question: Make sure there are no duplicate characters in a string. Hopefully, I read that right. If I did, here's what I did:

I'll be writing this in Python as my Java knowledge is limited. I may edit in a Java version at some point.

My first thought was this: a counter. That bit was obvious. I would also need a way of checking for all of the letters. After some research, as I didn't know the right way to check for duplicate letters, I found the .count() function being used and worked from there. It would return an int that was equal to how many times the letter occurred in the string.
I thought "Ok, I'll need to end it with an if statement obviously".
Based on that I decided on how I would write the program.
I would set an array with the full alphabet and run a for loop that went through each letter and ran .count() for that letter on the string. If it occurred only once in the string then I would just continue the loop, if it occurred more than once then I would add the amount of occurrences to the total. I could then use the total variable, after the for loop, in an if statement. If the total was greater than 0 (as it had been added to), then duplicates had been found.
However, if it was equal to 0, then no duplicates were found and all letters were unique.

I also ran .lower() and .replace(" ", "") on the string so that capitalization didn't affect it and spaces weren't counted as duplicate characters, just as a precaution.

This was to be my algorithm.

I set to writing the code and came up with this, but it wasn't the final solution:

letters = "abcdefghijklmnopqrstuvwxyz"


def Checker(string):

    string = string.replace(" ", "").lower()

    total = 0

    for l in letters:
        count = string.count(l)
        if count > 1:
            total += count

    if total > 0:
        print("Duplicates found.")
    else:
        print("No duplicates found.")


Checker("string") # Returns "No duplicates found."

After some thinking, I realized that this isn't exactly efficient as it goes through every letter in the alphabet despite the fact that some letters won't be in the string. I optimized the code so that it only checked the letters in the string, and not the whole alphabet. This is my complete code:

def Checker(string):
    string = string.replace(" ", "").lower()

    total = 0

    for l in string:
        count = string.count(l)
        if count > 1:
            total += count

    if total > 0:
        print("Duplicates found.")
    else:
        print("No duplicates found.")


Checker("string")

This also gets rid of the unnecessary letters array.
You can run some unit tests by simply changing the string in the parameter of the function call.

This code is simple, relatively efficient (there is probably a more efficient method out there somewhere), and looks elegant.
Hope you like it!
Thanks :slight_smile:

#3

Oops: I thought the FizzBuzz challenge was the challenge for this fortnight! Never mind, here goes for the duplicate letter challenge. I did this in Java to test myself a bit more, as it's not my strongest language.

It's interesting to think about the big-O for this solution. In the end, we have to carry out sequential comparisons until we get a match, so this has to be a O(N^2) solution. My first thought was to use an array of chars: as soon as one already exists, then the game is up. In pseudo code this would go something like

  if (myChar in arr) then found=true else arr.push(myChar)

but that is hiding a sequential search that gets longer as the array gets bigger, so it’s still really a O(N^2).

In any case, the challenge was to avoid using any new data structures. Therefore, it is easiest to compare letters pairwise and make sure we can short-circuit as soon as a match is found.

The other problem is defining “duplicates”. Do spaces count? Case significant? What about accents: e, è, é and so on? For simplicity, I have settled on a simple toUpperCase comparison, but it could be make as complex as you like!!

Here is my code:

class DuplicateLetters {

  private static final String DUPSFOUND = "duplicates found";
  private static final String NODUPS = "all unique";

  private static boolean sameLetter(char s1, char s2) {
    return (Character.toUpperCase(s1) == Character.toUpperCase(s2));
  }

  public static void main(String args[]) {

    String s = args[0];
    Boolean found=false;

    System.out.println(s);

mainloop:
    for(int i=1; i<s.length(); i++) {
      for (int j=0; j<i; j++) {
        if (sameLetter(s.charAt(i), s.charAt(j))) {
          found = true;
          break mainloop;
        }
      }
    }
    System.out.println(found ? DUPSFOUND : NODUPS);
  }
}

Hope you like it!
Tim F

#4

Hi,

I've been coding in python for about a year or so, mainly self-taught.

Here's my first function:

def char_checker(text):
    if len(text) == len(set(text)):
        print('all unique')
    else:
        print('duplicates found')
Updated with an explanation. 

def char_checker(text):
    '''check to see if there are repeated characters in text'''

    # Find the number of characters in the given text string
    num_char = len(text)

    # Find the unique characters in the string
    # set(iterable) iterates over the parameter to make a set.
    unique_char = set(text)

    # Find the number of unique characters in the string using
    #  properties of set datatype
    num_unique = len(unique_char)

    # If the total number of elements in the text equals the number of
    # unique elements in the text, then there are no repeated values.
    if num_char == num_unique:
        print('all unique')

    # If the number of elements doesn't match, then there is a character
    # that appears in the text more than once.
    else:
        print('duplicates found')

In python, a set is an unordered list of unique items. So no matter how many times an item is listed when you define a set, it is only listed once as an element of the set.

>>> s = {1,2,2,2,4,5,6,9}
>>> s
{1,2,4,5,6,9}
>>> s
{2,5,1,9,4,6}

Above, I defined a set and then called it twice. Note how the order of the elements of the set changed.

Based on the comment by @nstublen, I came up with something completely different.

Since I want to end this as soon as I find a duplicate value, I don't want to act on the entire string if it can be avoided.

I start by looping over the characters in the sting. The next step is to see if the character occurs more than once.

Here I'm using a try-except setup. Try is a cool feature that performs a task that could fail but doesn't break the program. You can add except conditions to handle specific errors.

The method str.index(str, beg=0 end=len(string)) locates a substring inside a string and returns the starting position of the substring. beg and end are optional features defining a portion of the string to be searched. I nested my method to so the search starts immediately to the right of the the position of the first occurrence of the substring (inner index call). If the substring is present, the method returns the position. If it is not present, the method returns ValueError.

If char is present the a second time, it will have a positive position which triggers the conditional and reports that there are duplicates and exits the function.

If the char is not present, the ValueError gets raised and we pass or do nothing.

A cool feature of for loops I saw on a YouTube video is that an else condition can be added to the loop if it runs through all of its values. So if the loop covers all of the characters in the string without finding a duplicate, it triggers the else condition and reports that there are no duplicates. 

def unique_char(text):
    '''check to see if there are repeated characters in text'''
    for char in text:
        try:
            if text.index(char, text.index(char) + 1) != -1:
                print('duplicates found')
                return
        except ValueError:
            pass
    else:
        print('all unique')

-Stoddard

#5

This is my solution for this problem in javascript:

var letters = "abcdgefghijklmnopqrstuvwxyz";

function checkLetter(string) {
    var strLength = string.length;
    var arr = [];
    for (var i = 0; i<strLength; i++){
        var subStr = string.substring(i,i+1);
        
        if(arr.find(function(letter) {return letter === subStr})){
            console.log('duplicates found.');
            return;
        };

        arr[i] = subStr;
    }
    console.log('all unique');
    return arr;
}
var result = checkLetter(letters);

But I am just learning It yet.

#6

Since I, not long ago, found out how set() in Python works, it was the first thing I tried:

def is_unique(s):
  return str(set(s)) == s

But since sets are unordered, and other minor reasons, this didn't work. Then I thought it through and realized I didn't need it to be ordered, just the same length, therefore:

def is_unique(s):
  return len(s) == len(set(s))

If it's stupid, but it works, it ain't stupid. And just to get the print:

print('all unique' if is_unique('Codecademy') else 'duplicates found')

I'm mostly self taught and I'd like if someone could tell me what a "data structure" is, thanks.

#7

Hello, first time submitting a solution so here we go.
Taking into account the 'Extra credit'
We can use string splicing to compare a single character of a string to all other characters of the same string.
Put that inside a for loop that goes through the entire length of the string and voila! This assumes the need for case sensitivity which could easily be fixed either the .upper() or .lower().
This will also count whitespace as a character.

test_string = input("Enter a string to test for character uniqeness : ")
unique_test = True
for i in range(0,len(test_string)):
    if test_string[i] in (test_string[:i] + test_string[i+1:]):
        unique_test = False
        break
if unique_test: print("all unique")
else: print("duplicates found")
#8

Maybe I misread but why cant you just use a regular expression to handle the check. I did this with javascript. And I have edited this to just expand more on my answer.

the regular expression allows me to set the format/constraints I want to test against then I can test against it using the test function. This will return a boolean that I then alert to notify the user of the test result.

var str="psdssda";
var stringCheck = (/([a-zA-Z]).*?\1/).test(str)        
alert(stringCheck);
#9

I decided to try out both the easy solution and the intermediate solution, i.e. without any additional data structures.

1. Easy solution

def unique_ez(str):
    return len(str) == len(set(str))

Since a set can only contain one of each element, converting the string to a set will eliminate all duplicates. If the original string has the same ammount of elements as the set with duplicates eliminated, then there are no duplicates.

Since insertion into a set has an average time complexity of O(1) (according to Python Wiki), this solution should have time complexity of about O(n), where n is the length of the string. (len(str) should also take linear time).

2. Intermediate solution

Here I'm not allowed to use a set or a list (if I understand the question correctly), so here's how I did it instead.

def unique_hard(str):
    str2 = ""
    for c in str:
        if c in str2: return False
        else:         str2 = str2 + c
    return True

I introduce a second string, and iterate through each character in the string. If the current character's in str2, it means there's a duplicate, and thus we can exit the loop early to avoid doing any more work. If not, we add it to str2 and proceed to the next iteration. If at any point, the same character appears again, c in str2 will return true this time meaning the duplicate has been detected.

Obviously the time complexity's a bit worse here. c in str2 takes O(m), where m is the current length of str2. The value of m in each iteration of the loop will be 0, 1, 2, ... n, since it increases by 1 each iteration. Since c in str2 takes O(m), if we add all iterations, it will take O(0+1+2+...+n) = O(n(n+1)/2) = O(n^2).

Not sure how string concatenation works in python since strings are immutable, so perhaps str2 = str2 + c reduces performance even further.

Here's the entire code: 

def unique_ez(str):
    return len(str) == len(set(str))

def unique_hard(str):
    str2 = ""
    for c in str:
        if c in str2: return False
        else:         str2 = str2 + c
    return True


string = input("please enter a string to test:\n")

if unique_hard(string): print("all unique")
else:                   print("duplicates found")
#10

@ross.rawlins It's at the right track

In Java I'd do something like

interface DuplicatedCharacterTester {    
    public static final String DUPLICATED_MESSAGE = "duplicates found";
    public static final String NON_DUPLICATED_MESSAGE = "all unique";

    static void test(String s) {
        System.out.println(
             s.matches("([\\w])*\`") ? DUPLICATED_MESSAGE
                : NON_DUPLICATED_MESSAGE
        );
    }
}

It's pretty simple, just check if it matches a regular expression.

#11

I chose to do this in JavaScript, mostly because that's what I'm learning right now.

I thought about a couple different ways of doing this. At first I thought about transforming the string into an array where each index of the array was a single character using string.prototype.split() and then iterating through the array with either nested for loops or by using array.prototype.splice() and then array.prototype.indexOf() with the spliced value. These both worked but didn't seem terribly efficient with all the transforming and extra variables.

After working on it for a bit a settled on a process where I would leave the string in tact and leverage string.prototype.indexOf() and string.prototype.slice() to do the heavy lifting. For those unfamiliar string.prototype.slice() accepts either 1 or 2 inputs. If only 1 input is given it returns the contents of the string including and after the index of the inputted value. If 2 inputs are given it returns all the contents of the string between the indices of the two inputted values.

Using these methods i settled on a algorithm where, using a for loop I would start with the first character in the string and check to see if there was another of the same character in the string using indexOf(). If no index was found, which is signified by the return of -1 then I would move onto the next character in the string and search for the same character in the rest of the string. I would no longer need to look at the previous characters because I had already compared them against the rest of the string, which means that with each pass the search area gets smaller and faster.

I would continue this up to the next to last character because using this algorithm the last character has already been compared to every other character in the string and it could only be compared against itself (which is not useful). 

"use strict";

let myString = 'abcdefghhijklmnopqrst';

function findUnique(string){
	for (let i=0; i < string.length -1; i++) { 
		if (string.slice(i+1).indexOf(string.slice(i,i+1)) != -1) return 'duplicates found';
	}
	return 'all unique';
}

console.log(findUnique(myString));
#12

I wrote in in JS, it works fine I guess.
Here is a link to my solution:
my code

function parse(){
    var input, testingStr, result;
    input = document.getElementById('myText').value;
    
    if (input.length <= 0) {
        document.getElementById('target').innerHTML = "enter a string";
        return;
    }

    testingStr = '';
    result = 'all unique';
    for (let i = 0; i < input.length; i ++){
        if (testingStr.indexOf(input[i]) > -1){
            // in other words return false
            result = 'duplicates found';
            break;
        }
        else {
            testingStr += input[i]
        }
    }
    // in other words return true
    document.getElementById('target').innerHTML = result
}

I get the user input > first thing I make sure it is not an empty string > then I create a testing string to keep track of the already tested characters > matching every char with the already examened string > if a match found I stop the loop and print the result 'dup found' if I got to the end of the loop I print 'all unique'.

End of my story :slight_smile:
It feels for me as the stright forward answer, although I am sure there are many approaches.
Would like to hear comments.

#13

My easy solution (though I like @coreblaster87817's solution better):

def dup_check(s):
    l = []
    for character in s:
        if character in l:
            print("duplicates found")
            return
        l.append(character)
    print("all unique")
    return

Pretty self-explanatory. It takes a string, initializes an empty list, iterates over the string checking each character against what is already in the list. If the character is already in the list, print "duplicates found" and return, otherwise, append the character to the list. If it gets through the entire string print "all unique."

#14 

res = "all unique"
for c in txt:
    if txt.count(c) > 1:
        res = "duplicates found"
        break
print(res)
#15

Here is my own approach. My code is java.
I used the toCharArray function of String class to "pick" each character of the string. This way I was easily able to compare chars of each string to check for duplicates using a for loop. Here's my code

void testString(String theString)
    {
        boolean duplicatesFound = false;
        String s = theString;

        char[] c = s.toCharArray();


       for ( int i = 0; i < c.length; i++ )
       {
          for (int j = i + 1; j < c.length; j++)
          {
              if (c[i] == c[j])
                  duplicatesFound = true;
          }
       }

        if (duplicatesFound)
            System.out.println("duplicates found");
        else
            System.out.println("all unique");

    }
#16

First implementation that came to my mind after tinkering with Python REPL for a minute:

def test(s):
   for letter in s:
     if s.count(letter) > 1:
       print("duplicate found")
       return
   print("all unique")

Step by step:

  • Iterate through every letter in the string
  • Check if the count of that letter is more than 1
  • If it is print "duplicate found" and return from method
  • After iterating through the string and finding no dupes print "all unique"

I guess that's what the challenge is about - finding a simple working solution fast.

#17 

var testString = "codecademy";
var flag = false;

function IsStringUnique(_string){
    for(var i = 0; i < _string.length; i++){
        var letter = _string[i];

        if(_string.slice(i + 1).indexOf(letter) != -1){
            console.log("Duplicates found. The letter: " + letter);
            flag = true;
        }  

    }
    if(!flag){
        console.log("All unique");
    }
}

IsStringUnique(testString);

The string 'codecademy' gets passed to the function 'IsStringUnique'.
The function then loops over every character of the string, which is possible because a string is just an array of characters.
For every iteration, the following happens:
1. The current letter gets assigned to a variable called 'letter'.
2. The parameter ('codecademy') gets sliced, removing the current letter from its array.
3. The letter variable (in #1) then gets looked up in what remains of the parameter after it got sliced. If a match is found (not a -1 position):
i. The letter gets logged to the console.
ii. A global variable called flag gets its value changed to true.
After the for loop completes, the value of flag gets checked. If it's still false, the message "All unique" gets logged to the console.

#18

The following is my solution. Unfortunately I didn't think about using the .test() method.

function uniqueOrNah(someString){
	var newObj = {};
	for(var i = 0; i < someString.length; i++){
		var curStr = someString[i];
		if(newObj[curStr] == null) {
			newObj[curStr] = 1;
		} else {
			console.log('Duplicate found')
			return;
		}
	}
	console.log('No duplicates')
}
#19

Using "set" function in python, you can find unique characters in a string. Compare the length of the result from set(string) to len(string) and you can determine if there are duplicates. Here is the code.

#20 

def is_unique(string):
    for i in range(len(string)):
        if string[i] in string[i + 1:]:
            print("duplicates found")
            return
    print("all unique")
    return

is_unique("teststr")

A simple Python 3.x solution looping through a string using indexing to compare the actual char to the rest of the string.