Checking for unique elements in a string vs. converting string to a set

I've seen the below "code1" used for checking for most frequently used characters in a string where each character is first checked for uniqueness rather than simply converting the string to a set (as in "code2"). Is the "code1" method preferred due to the slight performance improvement? And why is converting a string to a set more expensive than checking each element of the string if it already exists in a dictionary?

code1=

string = "This is an example string"
char_list = {}
for char in string:
    if char in char_list:
        char_list[char] += 1
    else:
        char_list[char] = 1

max_frequency = max(char_list.values())
chars_with_max_frequency = [key for key, value in char_list.items() if value == max_frequency]

code2=

string = "This is an example string"
char_list = {}
for char in set(string):
    char_list[char] = string.count(char)

max_frequency = max(char_list.values())
chars_with_max_frequency = [key for key, value in char_list.items() if value == max_frequency]

print("Method #1: Checking string for unique chars: %.4f" % timeit.timeit(code1,number=1000000))

print("Method #2: Converting string to set: %.4f" % timeit.timeit(code2,number=1000000))

Method #1: Checking string for unique chars: 2.6955

Method #2: Converting string to set: 3.4223

In the first method (code1), you are iterating through each character in the string and incrementing a counter for that character in a dictionary. The operation is O(n) because each character is being visited exactly once, where n is the length of the string.

In the second method (code2), after converting the string to a set (which eliminates duplicates and is an O(n) operation), you're invoking the string.count(char) method. This method itself is an O(n) operation because it needs to traverse the entire string to count occurrences of the character. As this is done for each unique character, the total operation becomes O(n^2). In the worst-case scenario, this could be as large as the length of the string itself.

So, to conclude, the conversion of the string to a set is not the expensive operation here. Instead, the expensive operation in the second method is the repeated use of the string.count() function. This is why the first method is faster than the second one.

in code 1 you are just checking the uniqueness of the elements and then incrementing a count. This require traversing through the string only once which has a time complexity of O(n) where n is the number of elements in the string.

but in code 2 you have to have to first convert string to a set and then count the number of elements. This will have a time complexity of O(n) * O(n) since we need to travel across the string once to convert it and then again traverse through it to count so it will give a time complexity of O(n^2).

Time complexity of O(n) is much better than O(n^2) so the first method is faster.

Your questions about both of your techniques have already been answered, so I'll add a third option leveraging the stdlib to count characters in a string :

from collections import Counter

counts = Counter('AABBCCDDAAADD')
sorted_keys = sorted(counts.items(), 
                     key=lambda x:x[1], 
                     reverse=True)

print(sorted_keys) 
# prints [('A', 5), ('D', 4), ('B', 2), ('C', 2)]

This will be two operations :

• O(n) on your inital strings, where n=strlen

• and O(nlogn) where n is the count of distinct characters in your string, which should be reasonnably small (unless you're working on some very diverse UTF-8 data)