javascript : find the first non repeating character
A classic interview question, I'm tired of not knowing the best answer for Javascript.
Please comment if you can improve upon it or have a better solution!
Cheers,
Jeff-
<html>
<script>
//var str = "hello please find the first non repeating character";
var str = "aacbdcee";
function find(str)
{
var start = str.split('');
var length = start.length;
var distinct = {};
//var distinct = {c:2, d:3, a:2, b:1, e:3}; // Build a new JS object that we can iterate like hash
for (var i = 0; i < length; i++) {
if(distinct[start[i]] && distinct[start[i]] >= 1) {
distinct[start[i]] = distinct[start[i]] + 1;
}
else {
distinct[start[i]] = 1;
}
}
for (var j in distinct) {
if (distinct[j] == 1) {
alert( j);
break;
}
else {
//alert('there are no repeating chars');
}
}
<script type="text/javascript">
function inArray(val, arr){
for(var i=0; i<arr.length; i++){
if(arr[i]==val){
return i;
}
}
return false;
}
function firstNonRepetitiveChar(str){
str = str.split('');
var distinct = [];
for(var i=0; i<str.length; i++)
{
var pos = inArray(str[i], distinct);
if( pos === false ){
// char not in distinct. insert it.
distinct.push(str[i]);
}else{
// char in distinct. remove it.
distinct.splice(pos, 1);
}
}
if(distinct[0]){
return distinct[0]
}
else{
return false
}
}
var str = "aacbdcee";
var first = firstNonRepetitiveChar(str);
if(first===false){
alert('there are no repeating chars');
}else{
alert('the first non repeating character is: '+first);
}
</script>
Instead of incrementing the number of appearances, we remove duplicates from distinct array. So only non-repeptitive characters will remain in array. At the first position is the non-repetitive char.
Last edited by hyperionXS; 02-20-2012 at 03:52 AM.
<script type="text/javascript">
var str = "aaacbdcee";
var rsl = str.split('').sort().join('').replace(/(\w)\1+/g,'').substr(0,1);
if(rsl) alert('the first non repeating character of '+str+' is: '+rsl);
else alert('All characters are repeated in '+str);
</script>
After sorting the letters, we use a back reference (\1 which represents the preceding sub-pattern : the letter) to remove all letters (\w) which appears twice or more (the + sign). Then the first letter, if any, was not repeated in initial string !
Edit : Sorry. This variant do not find exactly the first non repeating character but the alphabetically first non repeating character ! The following line would be better.
Code:
var str = "aaacbfbdcee",rsl;
while ((rsl=str.replace(/(\w)(\1+)/g,'').replace(/(\w)(\w+)(\1+)/g,'$2'))!=str) str=rsl;
rsl=rsl.substr(0,1);
if(rsl) alert('the first non repeating character is: '+rsl);
else alert(''All characters are repeated in ');
<script type="text/javascript">
var str = "aaacbdcee";
var rsl = str.split('').sort().join('').replace(/(\w)\1+/g,'').substr(0,1);
if(rsl) alert('the first non repeating character of '+str+' is: '+rsl);
else alert('All characters are repeated in '+str);
</script>
After sorting the letters, we use a back reference (\1 which represents the preceding sub-pattern : the letter) to remove all letters (\w) which appears twice or more (the + sign). Then the first letter, if any, was not repeated in initial string !
Not very efficient to remove non adjacent characters like in this example
Code:
var str="aaaccbdcbeefgh";
var rsl=str.replace(/(\w)\1+/g,"")[0];
alert(rsl);// give b which is repeated !
The solution seems to list the non repeated characters to remove all the others without sort
Code:
var nrp=str.split('').sort().join('').replace(/(\w)\1+/g,""); alert(nrp);
var rgx=new RegExp("[^"+nrp+"]+","g");alert(rgx);
var rsl=str.replace(rgx,'')[0];alert(rsl);
Not very efficient to remove non adjacent characters like in this example
Code:
var str="aaaccbdcbeefgh";
var rsl=str.replace(/(\w)\1+/g,"")[0];
alert(rsl);// give b which is repeated !
The solution seems to list the non repeated characters to remove all the others without sort
Code:
var nrp=str.split('').sort().join('').replace(/(\w)\1+/g,""); alert(nrp);
var rgx=new RegExp("[^"+nrp+"]+","g");alert(rgx);
var rsl=str.replace(rgx,'')[0];alert(rsl);
Thanks, the loop was not a very right method !
@007Julien
I see your second example contains a split/sort/join.
Why does it sort? I don't understand...
What do you mean by "without sort" ? (I still see a sort..)
Your example works, and it looks pretty efficient.
Does anybody know how to analyse it for big O?
Looks like O2, since it will touch every member of the string twice?
The difficulty consists in eliminating the not nearby repeated characters like b in the last example aaaccbdcbeefgh (when we eliminate c, we exceed the first one b and thus has to begin again the operation in a loop).
To resolve this one, without loop :
we sort at first the characters (an obtain aaabbcccdeefgh with this example) to eliminate those who are repeated and to list the others (dfgh),
then we build a regular expression with this alphabetically sorted list to eliminate all different characters of the non sorted initial list.
Finally, except better opinion, the best solution seems this one :
Code:
function firstNonRepeatedChar(str){
var nrp=str.split('').sort().join('').replace(/(\w)\1+/gi,"");
return str.replace(new RegExp("[^"+nrp+"]+","gi"),'').substr(0,1);
}
var arr="aacbdcee|aaaccbdcbeefgh|deBfcedfabCd|aaaccbgcbeefdh".split('|');
for (var i=0,l=arr.length;i<l;i++){
if (rsl=firstNonRepeatedChar(arr[i])) alert('the first non repeating character of \n '+arr[i]+'\n is '+rsl);
else alert('All characters are repeated in\n'+arr[i]);}
With an i to ignore the case and a substr(0,1), (witch return a more mathematical empty string than undefined), if all characters are repeated.
Oh, in "aaaccbgcbeefdh" the b is considered repeating? I would have called that the first unique character rather than the first non-repeating one. I was wondering why you were making your solutions so complicated, but I never noticed that you'd also eliminate those sort of situations!
Last edited by Declan1991; 02-21-2012 at 12:24 PM.
Great wit and madness are near allied, and fine a line their bounds divide.
<script type="text/javascript">
// http://www.w3schools.com/jsref/jsref_charat.asp
// http://www.w3schools.com/jsref/jsref_match.asp
// http://w3schools.com/jsref/jsref_replace.asp
// http://www.w3schools.com/jsref/jsref_obj_regexp.asp
var message, c, re, i;
var str = "aaacbcdcbeefgh";
for( i = 0; i < str.length; ) {
c = str.charAt(i);
re = new RegExp( c ,'g');
//alert(re);
if(str.match(re).length == 1) { message = 'The first non repeating character is: '+c ; break; }
str = str.replace( re,'');
}
//alert(message);
if(message == undefined) { alert('Tekrar etmeyen karakter yok.');}
else { alert(message) } // The first non repeating character is: d
</script>
Last edited by Ayşe; 02-21-2012 at 03:03 PM.
The Time Through Ages
In the Name of Allah, Most Gracious, Most Merciful
1. By the Time,
2. Verily Man is in loss,
3. Except such as have Faith, and do righteous deeds, and (join together) in the mutual enjoining of Truth, and of Patience and Constancy.
Repeated, unique, adjacent, nearby characters that is the question. Is'nt it?
The proposed solution do not work with upper-case letters, but in other cases it eliminate, without loop, all the characters appearing several times (adjacent or not) in the string.
Here is my assembler background showing up:
(1) Case sensitive.
(2) returns first non-repeating character in string, otherwise empty.
(3) Access var Y=new FnR(zz); c=Y.first('test string');
(4) Advantage: partial string scan. Full string scan only on repetitious strings.
(5) Future: Note whenever skip goes false an index to a new sub-pattern beginning can be made available.
<script type="text/javascript">
function FnR(text){ this.name=text; this.subPatterns=[0];
this.first= function(data){var j=0,base=0,baseC=data.charAt(0),skip=false;
while(++j<data.length){ if (baseC==data.charAt(j)) skip=true; else { if(!skip)return(baseC); skip=false;base=j;baseC= data.charAt(j);} }
if (!skip) return(baseC);
return("");
}
}
var X=new FnR('one');
alert(X.first("AAssddddgggttkkkZZ"));
</script>
Last edited by WyCnet; 02-21-2012 at 04:53 PM.
Reason: add advatage, and note.
Sorry, my practice of the English language is insufficient : I have difficulty in understanding that b would be, even the first one, non-repeated character while it appears three times in the string !
The main part is however to have presented the solutions answering the various interpretations...
Reply With Quote
Originally Posted by 007Julien
Bookmarks