Find The String Appeared Once

Question

Given a string, write an algorithm to find the character inside that appeared only once. For example, the result for string “abaccdeff” is b.

Solution

We can use a hashtable to count the appearance times for each character. Then rescan the hashtable for the character that appeared only once. These two step take O(n) each, therefore the overall time complexity is O(n).

Example

def find_appeared_once(string): 
    
    # a hashtable 
    hashtable = {} 
    
    # loop for each char in string 
    for char in string: 
        if char not in hashtable: 
            hashtable[char] = 1 
        else: 
            hashtable[char] += 1 
    
    # find the item appeared only once 
    for char, count in hashtable.items(): 
        if count == 1: return char 
        
# main 
print find_appeared_once('abaccdeff')