Author |
Topic: First un-repeated character in a string (Read 1209 times) |
|
fiddler
Newbie
Posts: 17
|
 |
First un-repeated character in a string
« on: Dec 25th, 2009, 11:07pm » |
 Quote  Modify
|
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)
|
|
 IP Logged |
|
|
|
R
Senior Riddler
Addicted!!!
Gender: 
Posts: 502
|
|
Re: First un-repeated character in a string
« Reply #1 on: Dec 25th, 2009, 11:53pm » |
Quote Modify
|
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.
|
| « Last Edit: Dec 25th, 2009, 11:54pm by R » |
IP Logged |
The first experience seems like Magic, but the second tells you the Trick behind it.
|
|
|
fiddler
Newbie
Posts: 17
|
|
Re: First un-repeated character in a string
« Reply #2 on: Dec 26th, 2009, 12:02am » |
Quote Modify
|
@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??
|
| « Last Edit: Dec 26th, 2009, 12:03am by fiddler » |
IP Logged |
|
|
|
R
Senior Riddler
Addicted!!!
Gender:
Posts: 502
|
|
Re: First un-repeated character in a string
« Reply #3 on: Dec 26th, 2009, 2:24am » |
Quote Modify
|
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.
|
|
IP Logged |
The first experience seems like Magic, but the second tells you the Trick behind it.
|
|
|
bmudiam
Junior Member
Gender:
Posts: 55
|
|
Re: First un-repeated character in a string
« Reply #4 on: Dec 27th, 2009, 4:25pm » |
Quote Modify
|
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).
|
|
IP Logged |
“Nobody can go back and start a new beginning, but anyone can start today and make a new ending.” - Maria Robinson
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: First un-repeated character in a string
« Reply #5 on: Dec 28th, 2009, 2:27am » |
Quote Modify
|
on Dec 27th, 2009, 4:25pm, 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?
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
bmudiam
Junior Member
Gender:
Posts: 55
|
|
Re: First un-repeated character in a string
« Reply #6 on: Dec 28th, 2009, 3:29am » |
Quote Modify
|
My bad..I didn't notice the constant space complexity..I was only thinking about time complexity.
|
|
IP Logged |
“Nobody can go back and start a new beginning, but anyone can start today and make a new ending.” - Maria Robinson
|
|
|
bmudiam
Junior Member
Gender:
Posts: 55
|
|
Re: First un-repeated character in a string
« Reply #7 on: Dec 28th, 2009, 3:42am » |
Quote Modify
|
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.
|
|
IP Logged |
“Nobody can go back and start a new beginning, but anyone can start today and make a new ending.” - Maria Robinson
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: First un-repeated character in a string
« Reply #8 on: Dec 28th, 2009, 4:56am » |
Quote Modify
|
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.
|
| « Last Edit: Dec 28th, 2009, 5:35am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: First un-repeated character in a string
« Reply #9 on: Dec 28th, 2009, 6:20am » |
Quote Modify
|
on Dec 28th, 2009, 4:56am, 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.
|
|
IP Logged |
|
|
|
Ved
Junior Member
Gender:
Posts: 53
|
|
Re: First un-repeated character in a string
« Reply #10 on: Dec 30th, 2009, 10:41am » |
Quote Modify
|
on Dec 26th, 2009, 2:24am, 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 ?
|
|
IP Logged |
|
|
|
blackJack
Junior Member
2b \/ ~2b
Gender:
Posts: 55
|
|
Re: First un-repeated character in a string
« Reply #11 on: Jan 13th, 2010, 3:37am » |
Quote Modify
|
on Dec 26th, 2009, 2:24am, 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?
|
|
IP Logged |
|
|
|
bmudiam
Junior Member
Gender:
Posts: 55
|
|
Re: First un-repeated character in a string
« Reply #12 on: Jan 13th, 2010, 11:55am » |
Quote Modify
|
on Jan 13th, 2010, 3:37am, 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.
|
|
IP Logged |
“Nobody can go back and start a new beginning, but anyone can start today and make a new ending.” - Maria Robinson
|
|
|
bmudiam
Junior Member
Gender:
Posts: 55
|
|
Re: First un-repeated character in a string
« Reply #13 on: Jan 13th, 2010, 11:57am » |
Quote Modify
|
on Dec 28th, 2009, 6:20am, 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.
|
|
IP Logged |
“Nobody can go back and start a new beginning, but anyone can start today and make a new ending.” - Maria Robinson
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: First un-repeated character in a string
« Reply #14 on: Jan 14th, 2010, 6:32am » |
Quote Modify
|
'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.
|
|
IP Logged |
|
|
|
serenity
Newbie
Posts: 25
|
|
Re: First un-repeated character in a string
« Reply #15 on: Jan 15th, 2010, 1:01pm » |
Quote Modify
|
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 
|
|
IP Logged |
|
|
|
chandra
Newbie
Posts: 1
|
|
Re: First un-repeated character in a string
« Reply #16 on: Jan 24th, 2010, 10:29pm » |
Quote Modify
|
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).
|
|
IP Logged |
|
|
|
bmudiam
Junior Member
Gender:
Posts: 55
|
|
Re: First un-repeated character in a string
« Reply #17 on: Jan 24th, 2010, 10:56pm » |
Quote Modify
|
on Jan 24th, 2010, 10:29pm, 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.
|
|
IP Logged |
“Nobody can go back and start a new beginning, but anyone can start today and make a new ending.” - Maria Robinson
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: First un-repeated character in a string
« Reply #18 on: Jan 25th, 2010, 1:49am » |
Quote Modify
|
on Jan 24th, 2010, 10:56pm, 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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
bmudiam
Junior Member
Gender:
Posts: 55
|
|
Re: First un-repeated character in a string
« Reply #19 on: Jan 25th, 2010, 6:09pm » |
Quote Modify
|
on Jan 25th, 2010, 1:49am, 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.
|
|
IP Logged |
“Nobody can go back and start a new beginning, but anyone can start today and make a new ending.” - Maria Robinson
|
|
|
samlilith
Newbie
Gender:
Posts: 3
|
|
Re: First un-repeated character in a string
« Reply #20 on: Jan 27th, 2010, 5:13am » |
Quote Modify
|
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. 
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: First un-repeated character in a string
« Reply #21 on: Jan 27th, 2010, 5:24am » |
Quote Modify
|
on Jan 27th, 2010, 5:13am, samlilith wrote:| The character for which this occured is your first repeated character. |
|
But we want the first un-repeated one.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print