Unique character Algorithm with Python

In this post, we’re going to solve the greater questions we found on the Cracking the Coding Interview 6th Edition book using one of today’s most famous programming languages: Python. In the book, we find 189 programming interview questions, ranging from the basics to the trickiest algorithm problems. It’s a pretty decent book for those who want to face some challenging code questions and it’s really worth reading carefully.

For the first question, the possible recruiter asks us to “Implement an Algorithm to determine if a string has all unique characters” and suggests that we create at least one solution with no data structures usage.

Here, we’re going to use three different approaches to solve the problem: Dictionaries, a Set function and in the final solution we’ll look through the alphabet to figure out whether a character was already used or not in our string.

Hands-on Coding… 💻

string01 = "MyStRinG"
string02 = "MyStRIng IS RePeAting"

def normalized(input_string):
  input_string = input_string.replace(" ", "")
  return input_string.lower()

In our first approach, we’ll use the Dictionary data structure to store the string and go through each character.

When the character is not yet inserted in the dictionary the program will go to the next step and add the value of “1” in the dictionary. Once the value is already stored in the data structure, we go to the next character and check if it exists in the dictionary, once it’s already there, we simply return False.

def dict_unique(input_string):
  dictionary = dict()
  for i in input_string:
    if i in dictionary:
      return False
    else:
      dictionary[i] = 1
  return True

To test our program, we’ll create two variables that’ll receive the normalized strings called unique_string and nonuniquestring and print the result of the normalized function call and then print the result for the dict_unique function verification.

string01 = "MyStRinG"
string02 = "MyStRIng IS RePeAting"

def normalized(input_string):
  input_string = input_string.replace(" ", "")
  return input_string.lower()

def dict_unique(input_string):
  dictionary = dict()
  for i in input_string:
    if i in dictionary:
      return False
    else:
      dictionary[i] = 1
  return True

unique_string = normalized(string01)
non_unique_string = normalized(string02)

print(dict_unique(unique_string))
print(dict_unique(non_unique_string))
result$ python3 isunique.py
mystring
mystringisrepeating
True
False

Our second approach will use a Python function called Set. The sets module provides classes for building and manipulating unordered collections of unique elements, and that’s the key for using sets for this solution. Once the elements are finally normalized, we’ll check the if the length of our string is the same as the length of the set string, if it’s the same, we can guarantee the uniqueness and then return True.

string01 = "MyStRinG"
string02 = "MyStRIng IS RePeAting"

def normalized(input_string):
  input_string = input_string.replace(" ", "")
  return input_string.lower()

def set_unique(input_string):
  #checking if the length is equal
  return len(set(input_string)) == len(input_string)

unique_string = normalized(string01)
non_unique_string = normalized(string02)

print(set_unique(unique_string))
print(set_unique(non_unique_string))

In our third and final approach, we run through the list of characters in the string, if we already encountered a letter of the alphabet in that string, it’ll be removed from the alphabet variable that we defined, replacing the letter with “”, and then we go to the next character repeating the same process until we get to the end.

If we encountered the character in the normalized string more than once, the program will return False, once the letter was already removed from our alphabet variable.

string01 = "MyStRinG"
string02 = "MyStRIng IS RePeAting"

def normalized(input_string):
  input_string = input_string.replace(" ", "")
  return input_string.lower()

# Checking the occurrence in the alphabet
def alphabet_unique(input_string):
  alphabet = "abcdefghijklmnopqrstuvwxyz"
  for i in input_string:
    if i in alphabet:
      alphabet = alphabet.replace(i, "")
    else:
      return False
  return True


unique_string = normalized(string01)
non_unique_string = normalized(string02)

print(alphabet_unique(unique_string))
print(alphabet_unique(non_unique_string))

Those were the three different ways to solve the “is unique” problem found in the Cracking Coding Interview book with Python. You can find the solution for that and many other data structures problems in my Github.

Stay tuned for more data structures problems and solutions with Python in this website!

It’s important to remember that I’m open to recommendations and constructive criticism to grow this communication channel and find better ways to share relevant contents with you! See you next time!

If it was helpful to you, consider buying me a coffee!

ko-fi

Published 11 Apr 2019

Software Developer & Computer Scientist. Driven by passion.
Prsc. 👩🏼‍🚀 on Twitter