You've successfully subscribed to Nicholas Workshop
Great! Next, complete checkout for full access to Nicholas Workshop
Welcome back! You've successfully signed in.
Success! Your account is fully activated, you now have access to all content.
Success! Your billing info is updated.
Billing info update failed.

Find The String Appeared Once

Nicholas Wong
Nicholas Wong

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')
Algorithm

Nicholas Wong

Fullstack software engineer with strong background in computer science and extensive experience in software engineering and architecture. Studied in NYU, worked in Yahoo, Rakuten and Manulife.