Python- What is the most efficient way to tell if a given string has only 1 character duplicated in it?

Question

Came across a question awhile ago, and it got me wondering what the best way to go about this would be.

Would like to have an method which takes an input string and returns a boolean whether or not the given string has only 1 character duplicated in it (can be duplicated multiple times)

ie: 'abca' -> True , 'abab' -> False, 'aaaa' -> True

My solution seemed a bit convoluted and I wanted to know a better way

#!/usr/bin/env python
import collections

def hasOnlyOneDuplicate(string):
    # turn string into a dictionary with counter and obtain a list of all the values/occurences of each letter
    values = list(collections.Counter(string).values())
    # then we remove all the numbers that are a 1
    result = filter(lambda a: a!=1, values)
    return len(result) == 1

If the given string only had 1 duplicated character in there, the length of the remaining list should be 1, right? Otherwise there were multiple characters duplicated

Thanks for the help

Dev Anand · Answer 1 · 2018-01-31T17:30:58.510

2

There is an easy way to do it using set. I am using your example, 'abca'

def hasOnlyOneDuplicate(s):
   return len(set(a for a in s if s.count(a) > 1))==1

edited Jan 31 '18 at 17:30

answered Jan 31 '18 at 16:36

Dev Anand

64
5

Using Counter can be comparatively slow, see this https://stackoverflow.com/questions/25706136/efficiently-find-repeated-characters-in-a-string/25706298#25706298 – Dev Anand Jan 31 '18 at 16:46
1

I like the simplicity of this answer (+1), but why bother with `x`? You could just use `[a for a in s if s.count(a) > 1]`. Also -- perhaps you can edit your answer to include your comment as part of the answer. – John Coleman Jan 31 '18 at 16:50
1

useless use of `[]`, bad `if True: return True; else: return False`, quadratic behaviour, unnecessary `list()` since `str.count()` exists. – Jan 31 '18 at 17:05

pault · Accepted Answer · 2018-02-05T20:31:02.110

Another method using str.count() and a short circuiting dupe counter:

def hasOnlyOneDuplicate(s):
    nDupes = 0
    for ch in set(s):
        if s.count(ch) > 1:
            nDupes += 1
        if nDupes > 1:
            return False
    return (nDupes == 1)

Update

This solution is the fastest, especially for long word lengths:

from collections import Counter
import string
import random

def hasOnlyOneDuplicate_pault(s):
    nDupes = 0
    for ch in set(s):
        if s.count(ch) > 1:
            nDupes += 1
        if nDupes > 1:
            return False
    return (nDupes == 1)

def hasOnlyOneDuplicate_dev(s):
    x = list(s)
    if len(set([a for a in x if x.count(a) > 1]))==1: 
        return True 
    else: 
        return False

def hasOnlyOneDuplicate_john(s):
     return len([c for c,v in Counter(s).items() if v > 1]) == 1

N = 1000
test_words = [
    ''.join(random.choice(string.lowercase) for _ in range(random.randint(3,30)))
    for _ in range(N)
]

%%timeit
len([hasOnlyOneDuplicate_pault(s) for s in test_words])
# 100 loops, best of 3: 2.57 ms per loop

%%timeit
len([hasOnlyOneDuplicate_dev(s) for s in test_words])
# 100 loops, best of 3: 7.6 ms per loop

%%timeit
len([hasOnlyOneDuplicate_john(s) for s in test_words])
# 100 loops, best of 3: 9.61 ms per loop

Update 2

All posted answers are faster than OP's solution:

%%timeit
len([hasOnlyOneDuplicate(s) for s in test_words])
# 100 loops, best of 3: 10.9 ms per loop

Short circuiting definitely makes sense, especially if the string is at all long. — John Coleman, Jan 31 '18 at 16:54
comprehension-based 1-liners are fun to write but are not always the most efficient, as your results show. I was considering deleting my answer but what will leave it up as a useful comparison to your answer (which warrants being the accepted answer). — John Coleman, Jan 31 '18 at 17:04

score 1 · Answer 3 · answered Jan 31 '18 at 16:08

1

Here is another way:

from collections import Counter

def hasOnlyOneDuplicate(s):
     return len([c for c,v in Counter(s).items() if v > 1]) == 1

Using a comprehension rather than filter and lambda is more pythonic.

answered Jan 31 '18 at 16:08

John Coleman

51,337
7
54
119

1

you only have to check the second element of `.most_common(2)`. – Jan 31 '18 at 16:33
@hop good observation (I wasn't aware of that counter method) -- although some caution would need to be taken with strings like `"aaaaaa"`. Perhaps you could turn your comment into an answer. – John Coleman Jan 31 '18 at 16:43

Python- What is the most efficient way to tell if a given string has only 1 character duplicated in it?

3 Answers3