how to use python to find the first not repeating character?

Question

I am solving a problem: Given a string s consisting of small English letters, find and return the first instance of a non-repeating character in it. If there is no such character, return '_'.

For example: s = "abacabad", the output should be firstNotRepeatingCharacter(s) = 'c'.

I wrote a simple code, it got through all the test, but when I submit it, it reports error, anyone know what's wrong with my code? Thank you!

def firstNotRepeatingCharacter(s):   
    for i in list(s):
        if list(s).count(i) == 1:
            return i
    return '_'

Does this answer your question? Counting Letter Frequency in a String (Python) — Harun Yilmaz
– Harun Yilmaz, Commented Sep 17, 2020 at 7:15
Tests passed: 15/19. Execution time limit exceeded on test 16: Program exceeded the execution time limit. Make sure that it completes execution in a few seconds for any possible input. — Qing
– Qing, Commented Sep 17, 2020 at 7:16
I am practice on a website, maybe because my code was too slow? There is better code? — Qing
– Qing, Commented Sep 17, 2020 at 7:17
@Qing according to the error ` Execution time limit exceeded` your code is slower than what the test demands — Alex Mandelias
– Alex Mandelias, Commented Sep 17, 2020 at 7:33

user2390182 · Accepted Answer · 2020-09-17 07:27:22Z

5

Could be a performance issue as your repeated count (and unnecessary list conversions) calls make this approach quadratic. You should aim for a linear solution:

from collections import Counter

def firstNotRepeatingCharacter(s):   
    c = Counter(s)
    for i in s:
        if c[i] == 1:
            return i
    return '_'

You can also use next with a generator and a default value:

def firstNotRepeatingCharacter(s):   
    c = Counter(s)
    return next((i for i in s if c[i] == 1), '_')

If you can only use built-ins, just make your own counter (or any other data structure that allows you to identify duplicates)

def firstNotRepeatingCharacter(s):   
    c = {}
    for i in s:
        c[i] = c.get(i, 0) + 1
    return next((i for i in s if c[i] == 1), '_')

edited Sep 17, 2020 at 7:27

answered Sep 17, 2020 at 7:14

user2390182

73.7k6 gold badges71 silver badges95 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

Qing Over a year ago

I am practicing online on a website, it doesn't allow me to import anything... and the error was "Tests passed: 15/19. Execution time limit exceeded on test 16: Program exceeded the execution time limit. Make sure that it completes execution in a few seconds for any possible input." So I am wondering is it because my code was too slow?

user2390182 Over a year ago

@Qing I added a linear approach using only built-ins. And yes, for large input data (e.g. strings with 10^5 chars), your solution will become very slow.

Qing Over a year ago

Thank you very much! But I don't understand why my code was wrong?

user2390182 Over a year ago

Not wrong, but slow because of the (underlying) nested loop algorithm: "for each char in string -> count that char in the string". The linear approaches I suggest count all chars in a single iteration and then use that information in a second iteration.

Qing Over a year ago

Oh that make sense. Much appreciated!

Jay Patel · Accepted Answer · 2021-12-21 16:40:34Z

2

The task at hand is to find first non repeating character from a given string e.g. s = 'aabsacbhsba'

def solution(s):
    # This will take each character from the given string s one at a time 
    for i in s: 
        if s.index(i) == s.rindex(i): # rindex() returns last index of i in s 
            return i  
    return  '_'

Here s.rindex(i) method finds the last occurrence of the specified value [value at i in s in our case] we are comparing it with current index s.index(i), if they return the same value we found the first occurance of specified value which is not repeated

You can find definition and usage of rindex() at : W3School rindex()

edited Dec 21, 2021 at 16:40

answered Dec 20, 2021 at 20:45

Jay Patel

314 bronze badges

2 Comments

General Grievance Over a year ago

I think you can make this faster, but I suppose this will work if it's just lowercase.

Jay Patel Over a year ago

Since the question says that string s consists of lowercase characters it should give correct answer all the times. In case we are using this to find first occurrence of a non-repeating character which includes both upper and lower case characters, we can just use s.lower() to convert the given string to lowercase and then we can proceed to find our character.

Collectives™ on Stack Overflow

how to use python to find the first not repeating character?

2 Answers 2

5 Comments

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

5 Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related