www.webdeveloper.com
Page 1 of 2 12 LastLast
Results 1 to 15 of 29

Thread: javascript : find the first non repeating character

  1. #1
    Join Date
    Feb 2012
    Posts
    7

    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');
    }
    }

    }

    find(str);

    </script>
    </html>

  2. #2
    Join Date
    Feb 2012
    Posts
    218
    Code:
    <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.

  3. #3
    Join Date
    Oct 2010
    Location
    Versailles, France
    Posts
    1,264
    A variant
    Code:
    <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 ');
    Last edited by 007Julien; 02-20-2012 at 06:21 AM.

  4. #4
    Join Date
    Feb 2012
    Posts
    218
    Quote Originally Posted by 007Julien View Post
    A variant
    Code:
    <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 !
    WOW. that is nice ! very good method !

  5. #5
    Join Date
    Aug 2007
    Posts
    3,767
    This is probably shorter and more efficient that the loop. Returns undefined if no non-repeating character.
    Code:
    "aaaccbdcee".replace(/(\w)\1+/g,"")[0];
    Great wit and madness are near allied, and fine a line their bounds divide.

  6. #6
    Join Date
    Oct 2010
    Location
    Versailles, France
    Posts
    1,264
    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 !
    Last edited by 007Julien; 02-20-2012 at 09:21 AM.

  7. #7
    Join Date
    Feb 2012
    Posts
    7
    Quote Originally Posted by 007Julien View Post
    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?

  8. #8
    Join Date
    Oct 2010
    Location
    Versailles, France
    Posts
    1,264
    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.
    Last edited by 007Julien; 02-21-2012 at 06:30 AM.

  9. #9
    Join Date
    Aug 2007
    Posts
    3,767
    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.

  10. #10
    Join Date
    Sep 2007
    Posts
    315
    Code:
      
     <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.
    Bismillahirrahmanirrahîm
    Hamd, Âlemlerin Rabbi, Rahmân, Rahîm, hesap ve ceza gününün (ahiret gününün) maliki Allah'a mahsustur. (Allahım!) Yalnız sana ibadet ederiz ve yalnız senden yardım dileriz. Bizi doğru yola, kendilerine nimet verdiklerinin yoluna ilet; gazaba uğrayanların ve sapıklarınkine değil.

  11. #11
    Join Date
    Oct 2010
    Location
    Versailles, France
    Posts
    1,264
    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.

    United we stand, divided we fall !

  12. #12
    Join Date
    Feb 2012
    Location
    youTUBE
    Posts
    234
    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.

  13. #13
    Join Date
    Aug 2007
    Posts
    3,767
    Quote Originally Posted by 007Julien View Post
    Repeated, unique, adjacent, nearby characters that is the question. Is'nt it?
    I'm asking! If I was asked to find the first non-repeating character, I'd consider "babb", b to be the answer.
    Great wit and madness are near allied, and fine a line their bounds divide.

  14. #14
    Join Date
    Oct 2010
    Location
    Versailles, France
    Posts
    1,264
    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...

  15. #15
    Join Date
    Feb 2012
    Location
    youTUBE
    Posts
    234
    Quote Originally Posted by Declan1991 View Post
    I'm asking! If I was asked to find the first non-repeating character, I'd consider "babb", b to be the answer.
    You are correct, the whole string needs to be checked, therefore I withdraw my solution.

Thread Information

Users Browsing this Thread

There are currently 1 users browsing this thread. (0 members and 1 guests)

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  
HTML5 Development Center



Recent Articles