1

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 '_'
Qing
  • 63
  • 1
  • 2
  • 8
  • 1
    *What* error...? – deceze Sep 17 '20 at 07:12
  • Does this answer your question? [Counting Letter Frequency in a String (Python)](https://stackoverflow.com/questions/40985203/counting-letter-frequency-in-a-string-python) – Harun Yilmaz Sep 17 '20 at 07: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 Sep 17 '20 at 07:16
  • I am practice on a website, maybe because my code was too slow? There is better code? – Qing Sep 17 '20 at 07:17
  • @Qing according to the error ` Execution time limit exceeded` your code is slower than what the test demands – Alex Mandelias Sep 17 '20 at 07:33
  • Yeah I realized that. I need to work on that :/ Thank you! – Qing Sep 17 '20 at 07:52

2 Answers2

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), '_')
user2390182
  • 72,016
  • 6
  • 67
  • 89
  • 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? – Qing Sep 17 '20 at 07:18
  • @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. – user2390182 Sep 17 '20 at 07:22
  • Thank you very much! But I don't understand why my code was wrong? – Qing Sep 17 '20 at 07:22
  • 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. – user2390182 Sep 17 '20 at 07:24
  • Oh that make sense. Much appreciated! – Qing Sep 17 '20 at 07:27
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()

Jay Patel
  • 31
  • 4
  • I think you can make this faster, but I suppose this will work if it's just lowercase. – General Grievance Dec 21 '21 at 05:31
  • 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. – Jay Patel Dec 21 '21 at 16:51