Check if a string has all unique characters in python

Introduction

In this tutorial, we will create a python program to check if a string has all unique characters or not. We will solve this problem both using or not using any extra space or data structure.

So, before we move on, let's take a quick look at what you need to remember to solve this problem.

• There are 128 unique characters in ASCII Table.
• But there are 256 characters in the case of extended ASCII.
• String length cannot exceed 256.

Solving the problem using extra spaces

First, we will create an array(we'll create a python list here) of boolean values(True or False) of 128 lengths. If we take 'i' represents the index then, the flag(True or False) at index 'i' will indicate whether the character 'i' is present in the string or not.

In this case, we are assuming the characters present in the given string are normal ASCII characters. If the character set belongs to extended ASCII, we need to increase the length of the boolean array.

Let's dive into the code directly.

Code

# function to determine the given string
def isUnique(str):
    # if the length of the given string
    # exceed 128, it will return False
    if len(str) > 128:
        return False

    # Declaring a list of 128 length
    # containing only bool(False) value
    char_set = [False for i in range(0, 128)]

    for i in range(0, len(str)):
        # storing the value of index i into
        # 'val' variable
        val = str[i]
        # Checking the flag at index i
        # where i = ASCII number of 'val'.
        # If the code found 'True' there,
        # it means the character is present more than
        # one time in the given string
        if char_set[ord(val)]:
            return False
        # Otherwise, returns True
        char_set[ord(val)] = True
    return True

if __name__=="__main__":
    # Given String
    str = 'Python'
    if isUnique(str):
        print("All characters are unique")
    else:
        print("Character redundancy exists")

Output

1. For the given string: 'Python', the output is

All characters are unique

2. For the given string: 'PySeek', the output is

Character redundancy exists

Complexity Analysis

Condition: If the length of the string is 'n', and the character set is fixed

Time Complexity: O(n)

Space Complexity: O(1)

Condition: If the character set is not fixed(might be ASCII or Extended ASCII), and the character set is 'c'

Time Complexity: O(c)

Space Complexity: O(c)

Solving the problem without using extra spaces

Now, we will solve the same problem without using any extra spaces(or data structure). In this case, we will use a factor of eight using a bit vector.

Important Note: Here, we're assuming only lowercase letters(a to z) are present in the given string.

Code

def isUnique(str):
    checker  = 0
    for i in range(0, len(str)):
        val = ord(str[i]) - ord('a')
        if (checker & (1<<val)) > 0:
            return False
        
        checker |= (1<<val)

    return True

if __name__=="__main__":
    str = 'abcde'
    if isUnique(str):
        print("All characters are unique")
    else:
        print("Character redundancy exists")

Output

1. For the given string: 'abcde', the output is

All characters are unique

2. For the given string: 'abcdefge', the output is

Character redundancy exists

Complexity Analysis

Condition: If the length of the string is 'n'

Time Complexity: O(n)

Space Complexity: O(1)

Summary

Here, we applied only two methods to solve this problem. For the first case, we used extra spaces to solve it. But, in the second method, we solved it without using any additional memory spaces.

There are many solution techniques too, for this problem:

1. You can iterate through the string and compare each character with the rest. It's a very easy method. But in this scenario, the Time Complexity will become O(n^2) and Space Complexity will be O(1).

2. You could sort the given string first, and then you can compare each character with the neighboring characters. In this case, the complexity(Time and Space both) will depend on the sorting technique you select.

Thanks for reading!💙

PySeek