15
\$\begingroup\$

I got this HW question from my freshman year at college - "Create a python function to check whether a string containing only lowercase letters has any repetition in it".

So, I did it a few ways:

  1. Brute forced it by checking if a character in the string was present in the substring to the right of it using a nested for loop.

  2. Created a list and stored every new character in it. Looped through each character in the string and checked if a character was in the list. If so, the string wasn't unique.

Both of these work but I'm looking for another solution. I came up with the following. Can you please tell me how inefficient this one would be?

def isUnique(string):
    ascii_product = 1
    for chr in string:
        ascii_prime = 2 ** (ord(chr) - 95) - 1
        if ascii_product % ascii_prime == 0:
            return False
        ascii_product *= ascii_prime
    else:
        return True

If the code is too horrible to understand, here's what I'm trying to do. I loop through each character in the string and with its ASCII value, I create a unique Mersenne prime number associated with it. I then check if the product is divisible by the prime. If it is, the string is not unique. Otherwise, I multiply the product by the prime.

This code works as well but I wanted to know how bad it is in terms of efficiency. Also, what's the best way of doing this?

\$\endgroup\$
3
  • 7
    \$\begingroup\$ "I create a unique Mersenne prime number". No you don't. ;) It's a creative idea, though. \$\endgroup\$ Nov 14 at 10:46
  • \$\begingroup\$ I got the logic wrong too... probably should have tried a few more values before thinking it worked \$\endgroup\$
    – 1d10t
    Nov 16 at 3:29
  • \$\begingroup\$ I think that if you indeed used prime numbers and not just 2**i - 1, the code would work. It would become really slow, e.g. with a long string of unique unicode chars, but it should work as far as I can tell. \$\endgroup\$ Nov 16 at 8:15
15
\$\begingroup\$

You should use sets which are an unordered collection without duplicates. Sets are a fundamental data structure found in many programming languages.

You should also strive to be a bit more Pythonic. A more natural solution would be as follows:

def is_unique(string: str) -> bool:
    return len(string) == len(set(string))

I have also used type hints which can also be omitted. Here, they convey that the argument to the function should be a string and return value a boolean. You can learn about later if you want to get more serious with Python.

\$\endgroup\$
8
  • \$\begingroup\$ A simple improvement to make this a valid answer would be at least to explain why you've changed isUnique to is_unique. \$\endgroup\$
    – AJNeufeld
    Nov 12 at 18:09
  • \$\begingroup\$ This is a cool solution. Thanks for sharing. Quick side question, how do I write more Pythonic code? Will reading other people's code help? \$\endgroup\$
    – 1d10t
    Nov 12 at 18:30
  • \$\begingroup\$ @AJNeufeld Thanks for the tip, I added some clarification. I hope someone else can chime in with a more deeper review. \$\endgroup\$
    – Juho
    Nov 12 at 18:35
  • \$\begingroup\$ @1d10t There are many ways in which you can get better. Reading other people's code, reading good books or other material, writing code & getting feedback... all of that should work more or less. \$\endgroup\$
    – Juho
    Nov 12 at 18:36
  • 2
    \$\begingroup\$ @1d10t "Pythonic" doesn't have a standardized meaning. However code which follow's PEP 8 tends to be more Pythonic than other code. Additionally things like Ned Batchelder's "Loop Like A Native" advice also makes code more Pythonic, however the idioms are common in other languages now too. \$\endgroup\$
    – Peilonrayz
    Nov 12 at 18:49
26
\$\begingroup\$

Naming

PEP 8: The Style Guide for Python Code has recommendations all Python programs should follow. One of these is function names should be in snake_case. As such, isUnique should actually be named is_unique.

Don't shadow built-in function names

chr is a built-in function. For example, chr(97) returns 'a'.

After executing for chr in string, you no longer have access to the chr function in that scope. ch is commonly used as a variable for extracting characters from a string.

for-else

The for ... else: ... construct is for use when you use break to terminate a loop early if something is found, executing the else: portion only if the search failed to find a result.

In this particular case, you are not using break; rather you return from inside the loop. In such as situation, else: is unnecessary, and can cause confusion. Consider:

def example(container):
    for item in container:
        if complicated_test(item):
            return True
    else:
        print("Point A")
    print("Point B")
    return False

There is no way "Point B" can be reached without also reaching "Point A" first. The else: is an unnecessary control block.

Magic numbers

What is 95? Where did it come from? It is a magic number. My first guess was that it is the ordinal of 'a', but that turned out to be wrong.

The constant deserves a name. LOWERCASE_TO_MERSENNE_OFFSET comes to mind as a possibility, though it might be a bit long. You might even want to define it with an expression, to help readers see where it comes from:

LOWERCASE_TO_MERSENNE_OFFSET = ord('a') - 2

Binary numbers

You are trying to use prime numbers to store flags in a single integer, to indicate whether or not a lowercase letter has been seen. Using bits to store these flags in a single integer is much simpler.

\$2^0\$ would be the 'a' flag, \$2^1\$ would be the 'b' flag, ... \$2^{25}\$ would be the 'z' flag

def is_unique(string: str) -> bool:
    """Determine if a string contains unique lowercase letters

    Returns `True` if all lowercase letters are unique, `False` otherwise.

    Calling the function with `string` containing anything other than
    lowercase letters results in undefined behaviour.
    """

    letter_flags = 0

    first = ord('a')
    for ch in string:
        flag = 1 << (ord(ch) - first)
        if letter_flags & flag:
            return False
        letter_flags |= flag

    return True

Since larger integers in Python are stored as objects on the heap, and are immutable, bit manipulation requires creating a new object when the bits of the integer are changed. As such, bit manipulation in Python is not as fast as in languages like C, C++, or Java.

There is a bitarray package which can be installed (pip install bitarray) which may be used to create mutable bit arrays. Using a bitarray instead of an integer will be much faster, yet still keeps the memory footprint of the application near its absolute minimum. Since a bitarray can be thought of as the bits of an integer, this can still be thought of as storing your “seen flags” in a single integer.

from bitarray import bitarray

def is_unique(string: str) -> bool:
    """Determine if a string contains unique lowercase letters

    Returns `True` if all lowercase letters are unique, `False` otherwise.

    Calling the function with `string` containing anything other than
    lowercase letters results in undefined behaviour.
    """

    letter_flags = bitarray(26)
    letter_flags.setall(False)

    first = ord('a')
    for ch in string:
        flag = ord(ch) - first
        if letter_flags[flag]:
            return False
        letter_flags[flag] = True

    return True

Finally, bit manipulation will always incur an overhead over direct indexing. Using a bytearray(26) object to hold the twenty-six flags is likely faster than using a bitarray. It is no longer meeting your implied goal of storing the flags inside a single integer. It requires perhaps 22 additional bytes of memory, but does not require installation of an external package.

def is_unique(string: str) -> bool:
    """Determine if a string contains unique lowercase letters

    Returns `True` if all lowercase letters are unique, `False` otherwise.

    Calling the function with `string` containing anything other than
    lowercase letters results in undefined behaviour.
    """

    letter_flags = bytearray(26)

    first = ord('a')
    for ch in string:
        flag = ord(ch) - first
        if letter_flags[flag]:
            return False
        letter_flags[flag] = 1

    return True

Set

Juho's set solution is a simple 1-line solution, but it is \$O(N)\$ in time. With certain inputs, it can take a very long time, failing programming challenges.

Eg) is_unique('a' * 1_000_000_000) calls the function with a string 1 billion characters long, and then iterates over the entire string to build the set. If you want to use this type of solution, you should include a fast fail to catch these types of degenerate cases:

from string import ascii_lowercase

def is_unique(string: str) -> bool:
    # Pigeon hole principle: a string longer than 26 characters must have duplicates!
    if len(string) > len(ascii_lowercase):
        return False

    return len(string) == len(set(string))
\$\endgroup\$
10
  • 3
    \$\begingroup\$ This site is amazing! I mean, this answer is extremely detailed and I learned a lot. Thank you so much for taking the time to do this. Is it ok to change the accepted answer? Even though I love Juho's solution, this answer is technically more of a review. And one last question - is it better to go with better efficiency or better readability? For example, lets imagine the pigeon hole principle wasn't applicable here and we had to go all the way to 1,000,000,000. So, in production code (not a competitive programming contest), would I use the set solution or the bit solution? \$\endgroup\$
    – 1d10t
    Nov 13 at 4:52
  • \$\begingroup\$ From What does it mean when an answer is "accepted"?: “Accepting an answer is not meant to be a definitive and final statement indicating that the question has now been answered perfectly. It simply means that the author received an answer that worked for them personally. Not every user comes back to accept an answer, and of those who do, they might not change the accepted answer even if a newer, better answer comes along later.”. a) you love Juho’s solution, so clearly it worked for you, b) you don’t need to accept a newer one \$\endgroup\$
    – AJNeufeld
    Nov 13 at 5:21
  • 1
    \$\begingroup\$ Different problems have different solutions. Given up to a billion integers from 1 to a billion, I’d use a bitarray to hold flags. Given a list of a few thousand integers from 1 to a billion, a set is better, because most of the range is unused. Given random words, a set is really the only viable solution, since there is no obvious unique mapping of words to numbers. Although the problems are similar, the details can change the preferred solution. \$\endgroup\$
    – AJNeufeld
    Nov 13 at 5:27
  • 3
    \$\begingroup\$ Re: efficiency -vs- readability: “code is usually written once and read many times”, and “premature optimization is the root of all evil”. Write clear, understandable code first. Only if it is not fast enough: profile it, and optimize only the code where the most time is spent. “90% of the time is usually spent in 10% of the code” \$\endgroup\$
    – AJNeufeld
    Nov 13 at 5:52
  • 3
    \$\begingroup\$ @idmean I disagree. I think my algorithm is actually \$O(1)\$. Sure the number of iterations initially increases by 1 for every additional character, but cannot exceed 26, which is a constant. Given a valid input string of 100, 1000, or a billion characters, it will execute in approximately the same time: 26 iterations or less. \$\endgroup\$
    – AJNeufeld
    Nov 15 at 1:24
10
\$\begingroup\$

Your solution is wrong.

For example, for isUnique('ca') you compute False. Because for 'c' you compute \$2^{4}-1 = 15\$, which is not a prime number. It's divisible by \$2^{2}-1 = 3\$ which you compute for 'a'.

If you want a simple formula for computing primes for the alphabet, I suggest Euler's \$n^2-n+41\$ (also see comments below).

\$\endgroup\$
6
  • \$\begingroup\$ Typo: \$`` n^2 - n + 41 ". \$ \$\endgroup\$
    – Nat
    Nov 15 at 12:24
  • \$\begingroup\$ @Nat If you think MathWorld made a typo, tell them, and if they fix it, let me know and I'll update my answer accordingly. \$\endgroup\$ Nov 15 at 13:58
  • 1
    \$\begingroup\$ Here (scanned PDF; translated PDF) shows Euler as giving \$ `` n^2 - n + 41 " .\$ \$\endgroup\$
    – Nat
    Nov 15 at 18:42
  • \$\begingroup\$ Admittedly that Mathworld page is a bit confusing. It claims that Legendre, not Euler, gave \$ `` n^2 - n + 41 " ,\$ despite that PDF that seems to show Euler giving it. But then that same Mathworld page has a table in which it credits Euler with \$ `` n^2 - n + 41 " .\$ \$\endgroup\$
    – Nat
    Nov 15 at 18:49
  • 1
    \$\begingroup\$ @Nat Thanks. I think in the table they standardized the polynomials so that they generate primes "when values from 0 to n are plugged in", as they say. So I wouldn't use that table as evidence. But when they initially wrote \$n^2+n+41\$, I think they reference the letter you showed, in which Euler wrote \$41-x+xx\$. Since \$n^2-n+41\$ is closer to that, I switched to that now. \$\endgroup\$ Nov 15 at 19:12
5
\$\begingroup\$

What is the meaning of “repetition” for this question? Same character used more than once or the same character used more than once sequentially?

Not that it matters that much as they can be treated almost the same. If the former, then checking if the string is longer than 26 characters (trivially true) and if not sorting the string, puts us into a position to look for the later (sequential appearance).

Sequential appearance is best handled by simply looping over all the characters in the string and returning true when we find a duplicate…

def is_unique_sq(string):
    if len(string)>26:
        return True
    prior_char = ''
    for current_char in sorted(string):
        if prior_char == current_char:
            return True
        prior_char=current_char
    return False

print(is_unique_sq("abcdc"))

While this could be solved in other ways (set, regexs), this is a straightforward solution so I wouldn’t consider it either over-engineering or premature optimization.

As for your solution, you are basically trying to use an integer as a dictionary, better to simply use a dictionary. For instance if your requirements had been: given a string with both upper and lower case characters, determine if any of the lower case characters appear more than once. Then using a dictionary would work. Some might say you were using it as an array, and if that is how you think of it, then use an array.

\$\endgroup\$
2
  • \$\begingroup\$ I apologise for the late reply, but it's for same character used more than once anywhere. Thanks for sharing this solution though, it just so happens to be one of the next HW questions :) \$\endgroup\$
    – 1d10t
    Nov 16 at 3:34
  • \$\begingroup\$ @1d10t: here’s my own late reply, changing to anywhere is trivial, and won’t have a significant impact because the input will be extremely short. \$\endgroup\$
    – jmoreno
    Nov 21 at 17:21
3
\$\begingroup\$

This code works as well but I wanted to know how bad it is in terms of efficiency.

Try it with the Python timeit module to measure the runtime of small code samples. It defaults to running the code a million times and tells you how long it takes. I put the string 'mchlrivughvm' which is 12 characters and has a dupe after 10 characters into some of the code on this page and got:

timeit (seconds) code
6.1 OP's prime code isUnique
2.8 AJNeufeld's bit flag code is_unique (surprisingly slow to me)
2.7 A for loop calling string.count(c) on every char in the string.
1.6 OP's O(N^2) nested loop
0.9 jmoreno's conecutive dupes check is_unique_sq
0.6 len(s) != len(set(s))

The problem with talking about the 'best way' of doing it in Python is that if you want shortest runtime, Python isn't the best language to do that. "Best" in Python is more likely to mean "clear and readable, performant enough not to be the bottleneck".

Code running down in the CPython runtime can be faster, even if it's algorithmically worse. Building a set() involves more conceptual things happening, but doing those in C is faster than doing "less work" of a single loop and using bit flags in Python. On small strings, your O(N^2) nested loop runs faster than the O(N) bit test. And as we've seen there won't be long strings because you can short-circuit any strings longer than 26 as they must contain duplicates.


how bad it is in terms of efficiency.

Take 2; how big might ascii_product *= ascii_prime get?

I think it could get to around 2**27 * 2**26 * 2**25 ... * 2**2 [1] which is something like this number:

4586997231980143023221641790604173881593129978336562247475177678773845752176969616140037106220251373109248

Compared with a typical max value of a 64bit signed integer:

9223372036854775807

As numbers go above what can fit in a 64 bit integer, Python will switch from hardware math to software math written in C which has huge overhead. Huge is relative, it's still fast enough to be useful on modern computers but compared to the processor working on native ints, it's many many times slower.

[1] I used 27-2 instead of 25-0 because you can't really have *0 or *1 in there. Multiplying by zero will reset, multiplying by one will not help.

\$\endgroup\$
6
  • \$\begingroup\$ I’ve added an explanation why bit manipulation is slow in Python, and added an optimized implementation using bitarray you might wish to add to your test results. \$\endgroup\$
    – AJNeufeld
    Nov 15 at 16:47
  • \$\begingroup\$ Timeit was very useful, thank you. This is one module I'm keeping for the rest of my life! \$\endgroup\$
    – 1d10t
    Nov 16 at 3:40
  • \$\begingroup\$ @AJNeufeld I tried; bitarray doesn't install because I don't have the right Visual C++ runtime versions, and your bytes() one does not run, throwing letter_flags[flag] = 1 TypeError: 'bytes' object does not support item assignment. (Using a list instead comes out about 1.9s) \$\endgroup\$ Nov 16 at 5:11
  • \$\begingroup\$ You can download precompiled bitarray wheels from lfd.uci.edu/~gohlke/pythonlibs/#bitarray Agh! I meant bytearray, not the read-only bytes object. Fixing... \$\endgroup\$
    – AJNeufeld
    Nov 16 at 6:37
  • \$\begingroup\$ “if you want shortest runtime, Python isn't the best language to do that.”, gets my +1. \$\endgroup\$
    – jmoreno
    Nov 16 at 13:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.