wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> First un-repeated character in a string
        
(Message started by: fiddler on Dec 25th, 2009, 11:07pm)
Title: First un-repeated character in a string
Post by fiddler on Dec 25th, 2009, 11:07pm
There is a string of characters and we have to find the first un-repeated character in it. eg - for string "abcab" ans is 'c'....
Space complexity : O(1) and T.C. : O(n)
Title: Re: First un-repeated character in a string
Post by R on Dec 25th, 2009, 11:53pm
For 8-bit characters make an array of 256 integers(initialized to 0s). Keep count of every character of string in it (One traversal for this). Now traverse the string again and print the first character whose count in the array is 1.
Title: Re: First un-repeated character in a string
Post by fiddler on Dec 26th, 2009, 12:02am
@R : Is there any other way to do this question with same space and time complexity other than maintaining a separate count array??  as in without hashing??
Title: Re: First un-repeated character in a string
Post by R on Dec 26th, 2009, 2:24am
You can do it by using an array of 8, 4-byte-integers, which gives you 256-bits to use as a bit-map. The only difference is that you'll be keeping one bit for each possible character, instead of keeping a whole integer, as in the count-array. Reading the string in the reverse order, you can keep track of the newest character you have seen.
Title: Re: First un-repeated character in a string
Post by bmudiam on Dec 27th, 2009, 4:25pm
I can think of a suffix tree solution, you can create a suffix for the string in O(N) and maintain the number of suffixes only for the nodes at height 1.

For abcab

the suffixes will be

abcab
bcab
cab
ab
b

Now only node with c literal will be having number of suffixes under it as 1, so you can find it by doing breadth first search for the nodes at level 1 and this can be achieved in O(N).
Title: Re: First un-repeated character in a string
Post by towr on Dec 28th, 2009, 2:27am

on 12/27/09 at 16:25:14, bmudiam wrote:
I can think of a suffix tree solution, you can create a suffix for the string in O(N) and maintain the number of suffixes only for the nodes at height 1.
How do you plan to build a suffix tree with only constant extra space?
Title: Re: First un-repeated character in a string
Post by bmudiam on Dec 28th, 2009, 3:29am
My bad..I didn't notice the constant space complexity..I was only thinking about time complexity.
Title: Re: First un-repeated character in a string
Post by bmudiam on Dec 28th, 2009, 3:42am
One can solve this in O(N^2) time complexity and constant space complexity by xoring each element with every other element. I don't think there is better solution than this other than using hashing(which is dependent on the domain of the data).

please correct me if i am wrong.
Title: Re: First un-repeated character in a string
Post by towr on Dec 28th, 2009, 4:56am
I don't see the point of xoring, since you can just compare each character against all the others.
But if you don't need to leave the string in tact, you can do better than O(n^2). For example you can just sort the character in the string in-place which would give O(n log n).
And if we're dealing with 8-bit characters, you can use a bitmap, as R already said, which gives O(n) behaviour.
Title: Re: First un-repeated character in a string
Post by Hippo on Dec 28th, 2009, 6:20am

on 12/28/09 at 04:56:34, towr wrote:
I don't see the point of xoring, since you can just compare each character against all the others.
But if you don't need to leave the string in tact, you can do better than O(n^2). For example you can just sort the character in the string in-place which would give O(n log n).
And if we're dealing with 8-bit characters, you can use a bitmap, as R already said, which gives O(n) behaviour.


If we are working with constant alphabet, the alphabet table would be O(1) space (O(n) time) solution.
And if you can destroy the string you can multiply time by the (used portion of alphabet) size and not use the table at all ... when checking for mutliplicity replace all occurences with the first character of the string (unless you have got solution) and don't check the first character twice.

If we use say UTF8 codded unicode (so the constant is bigger than n for regular inputs) the method cannot be used.

Just for clarity:
What answer should be given for input "zyxwzy"?

x ... first in the string ... sorting in place would not help.
w ... first in the alphabet ... permutations are not problem.
Title: Re: First un-repeated character in a string
Post by Ved on Dec 30th, 2009, 10:41am

on 12/26/09 at 02:24:46, R wrote:
You can do it by using an array of 8, 4-byte-integers, which gives you 256-bits to use as a bit-map. The only difference is that you'll be keeping one bit for each possible character, instead of keeping a whole integer, as in the count-array. Reading the string in the reverse order, you can keep track of the newest character you have seen.


R - not very clear, a bit of example perhaps ?
Title: Re: First un-repeated character in a string
Post by blackJack on Jan 13th, 2010, 3:37am

on 12/26/09 at 02:24:46, R wrote:
You can do it by using an array of 8, 4-byte-integers, which gives you 256-bits to use as a bit-map. The only difference is that you'll be keeping one bit for each possible character, instead of keeping a whole integer, as in the count-array. Reading the string in the reverse order, you can keep track of the newest character you have seen.


@R, how will tracking from the reverse help, anyways we have to look at whole of the array once completely and then one next traversal(from front) will be used for finding the first unique character. Am I wrong?

@bmudiam can we track the first unique character using suffix tree breadth first search?
Title: Re: First un-repeated character in a string
Post by bmudiam on Jan 13th, 2010, 11:55am

on 01/13/10 at 03:37:21, blackJack wrote:
@bmudiam can we track the first unique character using suffix tree breadth first search?


While building a suffix tree, its possible to keep additional information at the node saying the number of children nodes under a parent and breadth first search can be used to find the node.
Title: Re: First un-repeated character in a string
Post by bmudiam on Jan 13th, 2010, 11:57am

on 12/28/09 at 06:20:18, Hippo wrote:
And if you can destroy the string you can multiply time by the (used portion of alphabet) size and not use the table at all ... when checking for mutliplicity replace all occurences with the first character of the string (unless you have got solution) and don't check the first character twice.


@Hippo, can you please explain this.
Title: Re: First un-repeated character in a string
Post by Hippo on Jan 14th, 2010, 6:32am
'qweraqsredtspkmxxcewalrhefre' q is twice
'qqeraqsredtspkmxxceqalrhefre' w was twice
'qqqraqsrqdtspkmxxcqqalrhqfrq' e was 5 times
'qqqqaqsqqdtspkmxxcqqalqhqfqq' r was 4 times
'qqqqqqsqqdtspkmxxcqqqlqhqfqq' a was twice
'qqqqqqqqqdtqpkmxxcqqqlqhqfqq' q skipped, s twice
'qqqqqqqqqdtqpkmxxcqqqlqhqfqq' q skipped twice d is the solution.
Title: Re: First un-repeated character in a string
Post by serenity on Jan 15th, 2010, 1:01pm
I think it cant be done as we have to visit each character to evaluate O(N) n without storing it, its not possible to check unrepeated character ::)
Title: Re: First un-repeated character in a string
Post by chandra on Jan 24th, 2010, 10:29pm
array with constant size, say 256 entries  which stores three values: 0 -> element has not occurred, 1 -> element occurred once, 2 -> element occurred more than once.

first pass:
go through the string and set array[] with appropriate value.
 if array[char] == 0 then array[char] = 1; // first occurrence
if array[char] == 1 then array[char] = 2; // repeated
if array[char] == 2 then no-op;

second pass:
go through the string again and print char whose array[char] == 1.

2N time complexity and fixed space complexity (array of size 256).
Title: Re: First un-repeated character in a string
Post by bmudiam on Jan 24th, 2010, 10:56pm

on 01/24/10 at 22:29:22, chandra wrote:
array with constant size, say 256 entries  which stores three values: 0 -> element has not occurred, 1 -> element occurred once, 2 -> element occurred more than once.

first pass:
go through the string and set array[] with appropriate value.
 if array[char] == 0 then array[char] = 1; // first occurrence
if array[char] == 1 then array[char] = 2; // repeated
if array[char] == 2 then no-op;

second pass:
go through the string again and print char whose array[char] == 1.

2N time complexity and fixed space complexity (array of size 256).


I don't under how this solution will work. The question is not to find the first unrepeated character with the shortest ascii value but instead to find the first unrepeated character, no matter what its ascii value is.

For example:
cdac - should return d and not a.
Title: Re: First un-repeated character in a string
Post by towr on Jan 25th, 2010, 1:49am

on 01/24/10 at 22:56:03, bmudiam wrote:
I don't under how this solution will work. The question is not to find the first unrepeated character with the shortest ascii value but instead to find the first unrepeated character, no matter what its ascii value is.

For example:
cdac - should return d and not a.
I think he may have meant
"second pass:
go through the string again and print the first char whose array[char] == 1. "

Which is a solution that has been mentioned before.

In your example, d is the first character he would encounter for which array[char] == 1, so that would also be the answer he gives.
Title: Re: First un-repeated character in a string
Post by bmudiam on Jan 25th, 2010, 6:09pm

on 01/25/10 at 01:49:09, towr wrote:
I think he may have meant
"second pass:
go through the string again and print the first char whose array[char] == 1. "

Which is a solution that has been mentioned before.

In your example, d is the first character he would encounter for which array[char] == 1, so that would also be the answer he gives.



Thanks Towr and Chandra. Now I understood it.
Title: Re: First un-repeated character in a string
Post by samlilith on Jan 27th, 2010, 5:13am
I think there is no need for the 2nd pass....Take an array of size [256]... initialized to 0...Now keep reading the array given as input and if arr[char]==0 do arr[char]=1...and as soon as u find arr[char]=1 already...break and terminate the loop. The character for which this occured is your first repeated character.  ;)
Title: Re: First un-repeated character in a string
Post by towr on Jan 27th, 2010, 5:24am

on 01/27/10 at 05:13:43, samlilith wrote:
The character for which this occured is your first repeated character.  ;)
But we want the first un-repeated one.


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board