Question: Find all the characters, which are present in the character array given. The order of character should remain intact.

Example:
i/p: acdaacbdac
o/p: acdb

Answer: The naïve solution will be to have a result array and check for every character in input string in that. If the character is already present in the result, go to next character. This will be a O(n^2) solution. Print the result array, as it is to save the order. Lets see if we can find some better solution.

Lets have an array ‘result’ of 255 characters (to cover all characters). Initialize it to zero. Now for every element in input, set result[input[i]] to 1. So now ‘result’ array will have 1 at indexes, which are present in input and ‘0’ otherwise. Now in 2nd scan of input array, if result[input[i]] is 1, output it, make it ‘0’ else go on.

Algorithm:

1 n <- length(input) - 1
2 for i <- 1 to n
3 ....do result[input[i]] = 1

4 for i ← 1 to n
5 ....if result[input[i]]
6 ........do output = output + result[input[i]]
7 ........do result[input[i]] = 0

8 return result

Code: I have written the code in ruby. Also I have used Hash in pace of result array as I didn’t had much time. I have also checked if hash element already present or not.

def unique(string)
len = string.length
h = Hash.new
for i in 0..len-1
if not h[string[i]]
    h[string[i]] = 1
end
end


for i in 0..len-1
if h[string[i]] == 1
    p string[i]
    h.delete(string[i])
end
end
end

Complexity: Since we are just traversing the array twice. Complexity of this solution is O(n).

PS: One can use 1 bit per character to represent presence in the input array. But since we have just 255 length array, it won't help much in reducing space complexity.

Subscribe - To get an automatic feed of all future posts subscribe here, or to receive them via email go here and enter your email address in the box. You can also like us on facebook and follow me on Twitter @akashag1001.