DSA

https://en.wikipedia.org/wiki/List_of_algorithms

Cracking the Coding Interview

https://github.com/careercup/CtCI-6th-Edition

1.1

# Determine if a string has all unique characters

u = 'abcd'

def is_unique(s):
    # If the string is longer than the number of unique characters, it cannot be unique
    # 26 letters in the alphabet
    # 10 digits
    # 0-9, a-z, A-Z
    if len(s) > len(u):
        return False
    # Create a set to store unique characters
    char_set = set()
    # Iterate through the string
    for char in s:
        # If the character is already in the set, return False
        if char in char_set:
            return False
        # Add the character to the set
        char_set.add(char)
    # If the program has reached this point, all characters are unique
    return True

# Test the function
print(is_unique('a'))  # True
print(is_unique('abcda'))  # False
print(is_unique('abcde'))  # **False**
print(is_unique('aabbcc'))  # False
print(is_unique(''))  # True

What if you cannot use additional data structures?

SOLUTION

Start off with asking your interviewer if the string is an ASCII string or a Unicode string. This is an important question, and asking it will show an eye for detail and a deep understanding of Computer Science.

We'll assume for simplicity that the character set is ASCII. If not, we would need to increase the storage size, but the rest of the logic would be the same.

Given this, one simple optimization we can make to this problem is to automatically return false if the length of the string is greater than the number of unique characters in the alphabet.

Our first solution is to create an array of boolean values, where the flag at index i indicates whether character i in the alphabet is contained in the string.

If you run across this character a second time, you can immediately return false.