Interview Practice 17 - Find The String Appeared Once


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


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).

function to find char appeared once def find_appeared_once(string): hashtable = {} # a 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')

include <iostream.h> #include <string.h> char FirstNotRepeatingChar(char* pString) { if(!pString) return 0; const int tableSize = 256; unsigned int hashTable[tableSize]; for(unsigned int i = 0; i < tableSize; ++ i) hashTable[i] = 0; char* pHashKey = pString; while((pHashKey) != '/0') hashTable[(pHashKey++)] ++; pHashKey = pString; while(*pHashKey != '/0') { if(hashTable[*pHashKey] == 1) return *pHashKey; pHashKey++; } return pHashKey; } int main() { cout<<"请输入一串字符:"<<endl; char s[100]; cin>>s; char ps=s; cout<<FirstNotRepeatingChar(ps)<<endl; return 0; } ////////////////////////////////////////// 请输入一串字符: abaccdeff b Press any key to continue ///////////////////////////////////////////

Show Comments