4 ms·

Bored at work so I thought I'd try this one: "First non-repeated character in a string": char firstNonRepeatedChar(string s){ HashTable H; foreach(c

Bored at work so I thought I'd try this one: "First non-repeated character in a string": char firstNonRepeatedChar(string s){ HashTable H; foreach(char c in s) H[c]++; foreach(char c in s) if(H[c] == 1) return c; }

deleted 15y ago
[deleted]
kenjackson 15y ago
If you're still bored, what if the alphabet is small (say 26 characters), but string is typically huge (billions of characters) -- and on average the first repeated character is in the middle of the string. How does that change your algorithm?
- spaghetti 15y ago
  I assume you mean first non-repeated character. Anyways heres a possible performance improvement for a very long string: Assume the string is stored as a linked-list (so removing characters from the middle of the string is cheap). Then remove duplicates from the string during the initial traversal (keep track of unique characters that were removed as duplicates in a hashtable). After this single traversal the character in the head node of the remaining linked-list will be the first non-repeated character in the original string. Note the string must be stored in the linked-list initially... if we're responsible for moving the string from a theoretical array w/ billions of elements then we have to traverse the string twice just like the original algorithm and nothing is gained. Please clarify the "usually in the middle" part of your question. In this case do we always have to return the first non-repeated character? Or can we just be close?
  - kenjackson 15y ago
    Yes, first non-repeated, my bad. The usually in the middle is meant to say that typically the first character returned is position ~s.length/2. The linked list idea is good. I wasn't thinking of that at all.
    - spaghetti 15y ago
      One mistake I made: after the first traversal over the linked-list the character in the head node of the remaining list is not necessarily the first non-repeated character. Consider the string "aba" for example. However the second traversal will be over a shorter list... So this approach might get you somewhere :-)
- idunno246 15y ago
  It couldn't average in the middle, right? You're guaranteed one in the first 27(alphabet+1) characters, so just do it on that substring
  - kenjackson 15y ago
    What if most of the strings look like: "abcabcabcabc....abcabcxabcabcabcabc...abcabc"
  - idunno246 15y ago
    bleh, missread the non part
- cpeterso 15y ago
  Here's my Python implementation. It scans the string only once. It allocates at most 2*len(alphabet) characters while scanning the string. It also bails early if every character in the alphabet has been repeated. import string def first_nonrepeating_char(s, alphabet=string.printable): notrepeated = [] # remember order of appearance! repeated = [] # set of repeated chars, order unimportant for c in s: if c in notrepeated: # c has now been repeated! notrepeated.remove(c) repeated.append(c) if len(repeated) == len(alphabet): return None # every letter repeated! elif c not in repeated: # we have not seen c before notrepeated.append(c) return notrepeated[0] if len(notrepeated) > 0 else None assert first_nonrepeating_char('trait') == 'r' assert first_nonrepeating_char('aardvark') == 'd' assert first_nonrepeating_char('aabbac') == 'c' assert first_nonrepeating_char('aabacc') == 'b' assert first_nonrepeating_char('aaba ccdbe') == ' ' assert first_nonrepeating_char('aabad ccbe') == 'd'
  - kenjackson 15y ago
    Looks good. Although is [] associative in Python (haven't coded in Python in about 12 years)? The append method makes me think it isn't. If it's not then it goes from: O(n) where n is the length of the string to O(mn) where m is the length of the alphabet -- although m is small, so maybe not that bad of a deal, you could almost treat it is a constant factor, since it will be dwarfed by n. I do like the early exit.
    - cpeterso 15y ago
      Good point. Python's [] is a list (array). I considered using a Python dictionary, but that seemed wasteful for a small alphabet. Python does have a built-in set() class, which would have been more appropriate.

deleted 15y ago

[deleted]

kenjackson 15y ago

If you're still bored, what if the alphabet is small (say 26 characters), but string is typically huge (billions of characters) -- and on average the first repeated character is in the middle of the string. How does that change your algorithm?

spaghetti 15y ago
I assume you mean first non-repeated character. Anyways heres a possible performance improvement for a very long string: Assume the string is stored as a linked-list (so removing characters from the middle of the string is cheap). Then remove duplicates from the string during the initial traversal (keep track of unique characters that were removed as duplicates in a hashtable). After this single traversal the character in the head node of the remaining linked-list will be the first non-repeated character in the original string. Note the string must be stored in the linked-list initially... if we're responsible for moving the string from a theoretical array w/ billions of elements then we have to traverse the string twice just like the original algorithm and nothing is gained. Please clarify the "usually in the middle" part of your question. In this case do we always have to return the first non-repeated character? Or can we just be close?
- kenjackson 15y ago
  Yes, first non-repeated, my bad. The usually in the middle is meant to say that typically the first character returned is position ~s.length/2. The linked list idea is good. I wasn't thinking of that at all.
  - spaghetti 15y ago
    One mistake I made: after the first traversal over the linked-list the character in the head node of the remaining list is not necessarily the first non-repeated character. Consider the string "aba" for example. However the second traversal will be over a shorter list... So this approach might get you somewhere :-)
idunno246 15y ago
It couldn't average in the middle, right? You're guaranteed one in the first 27(alphabet+1) characters, so just do it on that substring
- kenjackson 15y ago
  What if most of the strings look like: "abcabcabcabc....abcabcxabcabcabcabc...abcabc"
- idunno246 15y ago
  bleh, missread the non part
cpeterso 15y ago
Here's my Python implementation. It scans the string only once. It allocates at most 2*len(alphabet) characters while scanning the string. It also bails early if every character in the alphabet has been repeated. import string def first_nonrepeating_char(s, alphabet=string.printable): notrepeated = [] # remember order of appearance! repeated = [] # set of repeated chars, order unimportant for c in s: if c in notrepeated: # c has now been repeated! notrepeated.remove(c) repeated.append(c) if len(repeated) == len(alphabet): return None # every letter repeated! elif c not in repeated: # we have not seen c before notrepeated.append(c) return notrepeated[0] if len(notrepeated) > 0 else None assert first_nonrepeating_char('trait') == 'r' assert first_nonrepeating_char('aardvark') == 'd' assert first_nonrepeating_char('aabbac') == 'c' assert first_nonrepeating_char('aabacc') == 'b' assert first_nonrepeating_char('aaba ccdbe') == ' ' assert first_nonrepeating_char('aabad ccbe') == 'd'
- kenjackson 15y ago
  Looks good. Although is [] associative in Python (haven't coded in Python in about 12 years)? The append method makes me think it isn't. If it's not then it goes from: O(n) where n is the length of the string to O(mn) where m is the length of the alphabet -- although m is small, so maybe not that bad of a deal, you could almost treat it is a constant factor, since it will be dwarfed by n. I do like the early exit.
  - cpeterso 15y ago
    Good point. Python's [] is a list (array). I considered using a Python dictionary, but that seemed wasteful for a small alphabet. Python does have a built-in set() class, which would have been more appropriate.