CODEWITHSUNDEEP
carraysstringalgorithmhashmap
chom
chom

Reputation: 285

Find the first non repetitive character in a string

I was asked this question in an interview. My answer: "create an array of size 26. Traverse the string by each character and make counts of characters in the array. Check the first non repetitive character by traversing again in the string and checking the array if the character is not repeated." What if the string contains large set of characters like 10000 types of characters instead of 26 types of alphabets.

Upvotes: 0

Views: 499

Answers (4)

jxh
jxh

Reputation: 70472

You can implement your original algorithm using less memory. Since you don't care about how many times the character repeated above 1, you only need 2 bits per character in the alphabet. When incrementing a value that is already above 1, just leave the value alone. The rest of your algorithm remains unchanged.

If memory is not a restriction, there is a faster algorithm that doesn't require another pass over the string. Allow each letter in the alphabet to be represented by a ListNode. Then have two lists, list1 and list2, that start out as empty. list1 contains letters that have only occurred once, and list2 contains letters that have occurred more than once. For each letter in the input string, get the corresponding ListNode, say node. If node is not in either list, put it at the end of list1. If node is already in list1, take it out, and put it in list2. After the input string is processed, if list1 is empty, there are no non-repeating characters. Otherwise, the character that corresponds with the first node in list1 is the first non-repeating character.

Follow this link to IDEONE for an implementation of the list based algorithm.

Upvotes: 2

Vinay Pandey
Vinay Pandey

Reputation: 1179

  1. Start reading the string character-by-character
  2. Put each character in HashMap
  3. Return the first character which has conflict

Pros: You don't need to create a BitMap/Bit-Array in advance

Cons: The HashMap can grow to as much as number of characters in string, if it does not encounter repeating character (or if there is no repeating character)

Upvotes: 0

user448810
user448810

Reputation: 17866

You gave the brute-force answer. A clever solution keeps an array of the size of the alphabet, we'll call it x, with each item initially -1. Then pass through the string once; if the current character has an x-value of -1, change it to the index of the current character, otherwise if the current character has an x-value greater than 0, change it to -2. At the end of the string, examine each location in the x array, keeping track of the smallest positive value and the associated character. I implement that algorithm in Scheme at my blog.

Upvotes: 1

OBu
OBu

Reputation: 5187

  • You could use a tree-like data structure instead of an array.
  • If our strings are not too long, loop through the string character by character and check, whether you manage to find it again. Drawback: n^2 runtime in the worst case
  • build a hash of each character for the first pass and then check each bucket seperately. Should be combined with the method above and I'm not sure whether it reduces runtime significantly - it depends on your real world data.

Upvotes: 0

Related Questions