you can find the link to the series homepage here
Non-repeating character in a string
In this part, we will look at a very simple problem of finding the non-repeating character in a given string
Import the ‘random’ module to create a random array, the ‘time’ module to record the execution time of the program and the string module to access the ASCII characters easily.
import random
import string
import time
a random array can be created like this:
# create a random string of 60000 lowercase characters
st_len = 60000
st = ‘’.join([random.choice(string.ascii_lowercase) for _ in range(st_len)])
this is just a decorator function to calculate the execution time of any function
| def time_it(func): | |
| def wrapper(*args, **kwargs): | |
| start = time.time() | |
| func(*args, **kwargs) | |
| end = time.time() | |
| return (end - start)*1000 | |
| return wrapper |
There are two ways to solve this problem. One is with a dictionary(hash map) and the other is with a set.
In the first method (dictionary), we will loop through the characters of the string and store the count of each character in a dictionary and then loop through the dictionary to find the character whose count is equal to one.
This method is the easiest to understand and implement. let’s look at the code
| #@time_it | |
| def dict_method(st): | |
| ''' | |
| This function will return the non-repeating | |
| characters in a string | |
| Args: | |
| st: the input string | |
| Return: | |
| unique: a list of characters that don't | |
| repeat in the string | |
| ''' | |
| d = {} | |
| for letter in st: | |
| if letter not in d : | |
| d[letter] = 1 | |
| else: | |
| d[letter] += 1 | |
| unique = [k for k,v in d.items() if v==1] | |
| return unique |
In the second method (set), we first initialize two sets and then loop through the characters of the string. For each character, we have to check if we have “seen it before”. To do that, we will use a set named ‘s’ to store all the unique characters that we have seen till now and we will use another set named ‘repeat’ to store the characters that were already present in the set ‘s’, that is if they repeat.
to get the letters that didn’t repeat, all we have to do is to subtract the ‘repeat’ set from the ‘s’ set. In simple words, the set ‘s’ stores all the alphabets in the given string and the set ‘repeat’ stores all the characters that repeated in the string.
let’s look at the code to further understand it better
| #@time_it | |
| def set_method(st): | |
| s = set() | |
| repeat = set() | |
| for letter in st: | |
| if letter in s: | |
| repeat.add(letter) | |
| else: | |
| s.add(letter) | |
| return s-repeat |
and since we are going through the string only once in both methods, the time complexity is O(n)
un-comment the @time_it line to return the execution time instead of the output
Data Dict 