return the first non repeating character in a string in javascript

If you're looking for the first occurrence of a letter that only occurs once, I would use another data structure to keep track of how many times each letter has been seen. This would let you do it with an O(n) rather than an O(n²) solution, except that n in this case is the larger of the difference between the smallest and largest character code or the length of the string and so not directly comparable.

Note: an earlier version of this used for-in - which in practice turns out to be incredibly slow. I've updated it to use the character codes as indexes to keep the look up as fast as possible. What we really need is a hash table but given the small values of N and the small, relative speed up, it's probably not worth it for this problem. In fact, you should prefer @Guffa's solution. I'm including mine only because I ended up learning a lot from it.

function firstNonRepeatedCharacter(string) {
   var counts = {};
   var i, minCode = 999999, maxCode = -1;
   for (i = 0; i < string.length; ++i) {
        var letter = string.charAt(i);
        var letterCode = string.charCodeAt(i);
       if (letterCode < minCode) {
           minCode = letterCode;
       }
       if (letterCode > maxCode) {
           maxCode = letterCode;
       }
        var count = counts[letterCode];
        if (count) {
           count.count = count.count + 1;
        }
        else {
            counts[letterCode] = { letter: letter, count: 1, index: i };
        }
   }

    var smallestIndex = string.length;
    for (i = minCode; i <= maxCode; ++i) {
       var count = counts[i];
       if (count && count.count === 1 && count.index < smallestIndex) {
          smallestIndex = count.index;
       }
   }

    return smallestIndex < string.length ? string.charAt(smallestIndex) : '';
}

See fiddle at http://jsfiddle.net/b2dE4/

Also a (slightly different than the comments) performance test at http://jsperf.com/24793051/2

var firstNonRepeatedCharacter = function(string) {
  var chars = string.split('');
  for (var i = 0; i < string.length; i++) {
    if (chars.filter(function(j) { 
                        return j == string.charAt(i); 
               }).length == 1) return string.charAt(i);
  }
};

So we create an array of all the characters, by splitting on anything.

Then, we loop through each character, and we filter the array we created, so we'll get an array of only those characters. If the length is ever 1, we know we have a non-repeated character.

Fiddle: http://jsfiddle.net/2FpZF/

We can keep track of frequency of each character of the string in an object. For example : for "aabcbd" we can store the frequency as

{ "a":2, "b":2, "c":1, "d":1 }

This will take O(n) time. Then we can traverse over this object and find the first character with frequency 1, which will also take O(n) time. So, the time complexity for this approach will be O(n).

const firstNonRepeating=(str)=>{
const obj={};
str.split("").forEach(item=>{
  obj[item] 
  ? obj[item]++ 
  : obj[item]=1;
});
const item = Object.keys(obj).find(key=> obj[key] === 1);
return item;
}

Note: I use ES6 Object.keys method which may not work in older browsers.

Two further possibilities, using ECMA5 array methods. Will return undefined if none exist.

Javascript

function firstNonRepeatedCharacter(string) {
    return string.split('').filter(function (character, index, obj) {
        return obj.indexOf(character) === obj.lastIndexOf(character);
    }).shift();
}

console.log(firstNonRepeatedCharacter('aabcbd'));

On jsFiddle

Or if you want a bit better performance, especially on longer strings.

Javascript

function firstNonRepeatedCharacter(string) {
    var first;

    string.split('').some(function (character, index, obj) {
        if(obj.indexOf(character) === obj.lastIndexOf(character)) {
            first = character;
            return true;
        }

        return false;
    });

    return first;
}

console.log(firstNonRepeatedCharacter('aabcbd'));

On jsFiddle

I came accross this while facing similar problem. Let me add my 2 lines. What I did is a similar to the Guffa's answer. But using both indexOf method and lastIndexOf.

My mehod:

function nonRepeated(str) {
   for(let i = 0; i < str.length; i++) {
      let j = str.charAt(i)
      if (str.indexOf(j) == str.lastIndexOf(j)) {
        return j;
      }
   }
   return null;
}

nonRepeated("aabcbd"); //c

Simply, indexOf() gets first occurrence of a character & lastIndexOf() gets the last occurrence. So when the first occurrence is also == the last occurence, it means there's just one the character.

Here's a Solution using Regex to replace all repeating characters and then returning the first character.

function firstNonRepeat(str) {

   // Sorting str so that all repeating characters will come together & replacing it with empty string and taking first character using substr.

   var rsl = str.split('').sort().join('').replace(/(\w)\1+/g,'').substr(0,1);

   if(rsl) return rsl;

   else return 'All characters are repeated in ' + str;

}

console.log(firstNonRepeat('aaabcccdeeef'));
console.log(firstNonRepeat('aaacbdcee'));
console.log(firstNonRepeat('aabcbd'));

First of all, start your loop at 1, not 0. There is no point in checking the first character to see if its repeating, obviously it can't be.

Now, within your loop, you have someString[i] and someString[i - 1]. They are the current and previous characters.

if someString[i] === someString[i - 1] then the characters are repeating, if someString[i] !== someString[i - 1] then they are not repeating, so you return someString[i]

I won't write the whole thing out for you, but hopefully the thought process behind this will help

 function FirstNotRepeatedChar(str) {
 var arr = str.split('');
 var result = '';
 var ctr = 0; 
  for (var x = 0; x < arr.length; x++) {
   ctr = 0;
  for (var y = 0; y < arr.length; y++) {
  if (arr[x] === arr[y]) {
    ctr+= 1;
    }
   }

if (ctr < 2) {
  result = arr[x];
  break;
  }
}
return result;
}
console.log(FirstNotRepeatedChar('asif shaik'));

Here's an O(n) solution with 2 ES6 Sets, one tracking all characters that have appeared and one tracking only chars that have appeared once. This solution takes advantage of the insertion order preserved by Set.

const firstNonRepeating = str => {
  const set = new Set();
  const finalSet = new Set();
  str.split('').forEach(char => {
    if (set.has(char)) finalSet.delete(char);
    else {
      set.add(char);
      finalSet.add(char);
    }
  })
  const iter = finalSet.values();
  return iter.next().value;
}

let arr = [10, 5, 3, 4, 3, 5, 6];
outer:for(let i=0;i<arr.length;i++){
    for(let j=0;j<arr.length;j++){
        if(arr[i]===arr[j+1]){
            console.log(arr[i]);
            break outer;
        }
    }
}


//or else you may try this way...
function firstDuplicate(arr) {
    let findFirst = new Set()
    for (element of arr)
        if (findFirst.has(element ))
            return element 
        else
            findFirst.add(element )
}

function firstUniqChar(str) {
    let myMap = new Map();
    for(let i = 0; i < str.length; i++) {
        let char = str.charAt(i);
        if(!myMap.has(char)) {
            myMap.set(char, 0);
        }
        myMap.set(char, myMap.get(char) + 1 );
    }
    for(let [key, value] of myMap) {
       if(value === 1) {
           return key;
       }
    }
    return null;
}

let result = firstUniqChar("caabbdccee");
console.log(result);

You can use Map Object and set key and value, where in value you store the count for that particular character, After that you can iterate over map and check where is value 1 and return that key.

Map Object remembers the original insertion order of the keys.

This solution should works with array with integers and string.

function firstNoneRepeating(list, map = new Map()) {
  for (let item of list) {
    if (map.has(item)) {
      map.set(item, map.get(item) + 1);
    } else {
      map.set(item, 1);
    }
  }
  for (let [key, value] of map.entries()) {
    if (value === 1) {
      return key;
    }
  }
}
console.log(firstNoneRepeating("aabcbd"));
console.log(firstNoneRepeating([5, 2, 3, 4, 2, 6, 7, 1, 2, 3]));

let str='aabcbd'
let ans=''
for (let i=0;i<str.length;i++){
    if(str.indexOf(str.charAt(i))===str.lastIndexOf(str.charAt(i))){
    ans+=str.charAt(i)
    break
    }
}
console.log(ans)

The question I was answering was [rightfully] closed as a duplicate of this one. But I think this answer offers something that the others miss: it is both O(n) and correct in the face of digits among the characters, which many answers here miss.

A first and perhaps naive approach would be to iterate through the characters and collect two results:

• a list of the characters ordered by their first appearance in the string
• a mapping of characters to their counts

So we might have intermediate data like this:

{order: ["s","w","i"], counts: {s: 3, w: 1, i: 1}}

or

{order: ["a","b","c"], counts: {a: 2, b: 2, c: 2}}

With that we can search that list, checking each character against the mapping until we find the first one with a count of 1.

Here is one version of that approach:

const findFirstNonRepeatingChar = (s) => {
  const {order, counts} = [...s].reduce(({order, counts}, c) => ({
    order: c in counts ? order : order.concat(c),
    counts: {...counts, [c]: (counts[c] || 0) + 1}
  }), {order: [], counts: {}})
  return order.find(c => counts[c] == 1) || null
}

console.log(findFirstNonRepeatingChar('swiss'))                 //=> 'w'
console.log(findFirstNonRepeatingChar('aabbcc'))                //=> null
console.log(findFirstNonRepeatingChar('abcdefabcdeabdgabh'))    //=> 'f'
console.log(findFirstNonRepeatingChar('abcdefabcdeabdgabhfgh')) //=> null

.as-console-wrapper {max-height: 100% !important; top: 0}

A sharp eye would note that we really seem to have all the information necessary in the counts Object. So it looks like we could use the intrinsic ordering of JS Objects to simplify this, with code something like this:

// WARNING: Broken implementation
const findFirstNonRepeatingChar = (s) =>
  (Object.entries(
    [...s].reduce((a, c) => ({...a, [c]: (a[c] || 0) + 1}), {})
  ).find(([k, v]) => v == 1) || [null])[0]

Instead of using a separate order object, we extract the entries from the generated counts and call find on that. It looks as though it works:

console.log(findFirstNonRepeatingChar('swiss'))                 //=> 'w'
console.log(findFirstNonRepeatingChar('aabbcc'))                //=> null
console.log(findFirstNonRepeatingChar('abcdefabcdeabdgabh'))    //=> 'f'
console.log(findFirstNonRepeatingChar('abcdefabcdeabdgabhfgh')) //=> null

But there's something broken here. The trouble is that Object iteration order is more complex than it first seems. According to the specification the first iteration keys are those strings that look like array indices, and they are iterated in numeric order, and only then the other keys are iterated, those in insertion order.

So introducing a digit will break this:

console.log(findFirstNonRepeatingChar('a0b'))                   //=> '0' -- OOPS!!

You can see this by expanding this snippet:

// WARNING: broken code
const findFirstNonRepeatingChar = (s) =>
  (Object.entries(
    [...s].reduce((a, c) => ({...a, [c]: (a[c] || 0) + 1}), {})
  ).find(([k, v]) => v == 1) || [null])[0]

console.log(findFirstNonRepeatingChar('swiss'))                 //=> 'w'
console.log(findFirstNonRepeatingChar('aabbcc'))                //=> null
console.log(findFirstNonRepeatingChar('abcdefabcdeabdgabh'))    //=> 'f'
console.log(findFirstNonRepeatingChar('abcdefabcdeabdgabhfgh')) //=> null

console.log(findFirstNonRepeatingChar('a0b'))                   //=> 'c' -- OOPS!!

.as-console-wrapper {max-height: 100% !important; top: 0}

We could fix this by using a Map rather than a plain object, with an implementation like this:

const findFirstNonRepeatingChar = (s) => {
  const counts = [...s].reduce((counts, c) => {
    counts.set(c, (counts.get(c) || 0) + 1); return counts
  }, new Map())
  return ([...counts.entries()].find(([k, v]) => v == 1) || [null])[0]
}

console.log(findFirstNonRepeatingChar('swiss'))                 //=> 'w'
console.log(findFirstNonRepeatingChar('aabbcc'))                //=> null
console.log(findFirstNonRepeatingChar('abcdefabcdeabdgabh'))    //=> 'f'
console.log(findFirstNonRepeatingChar('abcdefabcdeabdgabhfgh')) //=> null

console.log(findFirstNonRepeatingChar('a0b'))                   //=> 'a' -- Much better!

.as-console-wrapper {max-height: 100% !important; top: 0}

You can decide for yourself which implementation you like better. Even if that middle one worked, I would hesitate to use it. I prefer to think of objects as intrinsically unordered containers and never depend on their odd iteration order. The last one bothers me because of the mutation of the Map objects. I prefer to work with immutable data as much as possible. But you may have different priorities.

Fill an empty array with zeros, with same length as the string array, and tally up how many times they appear through the loop. Grab the first one in the tallied array with a value of 1.

function firstNotRepeatingCharacter(s) {
    const array = s.split("");
    let scores = new Array(array.length).fill(0);

    for (let char of array) {
        scores[array.indexOf(char)]++;
    }

    const singleChar = array[scores.indexOf(1)];
    return singleChar ? singleChar : "_"
}

You can iterate through each character to find() the first letter that returns a single match(). This will result in the first non-repeated character in the given string:

const first_nonrepeated_character = string => [...string].find(e => string.match(new RegExp(e, 'g')).length === 1);
const string = 'aabcbd';

console.log(first_nonrepeated_character(string)); // c

Here is my solution which have time complexity of o(n)

function getfirstNonRepeatingCharacterInAString(params) {
    let count = {};
    for (let i = 0; i < params.length; i++) {
        let count1 = 0;
        if (!count[params.charAt(i)]) {
            count[params.charAt(i)] = count1 + 1;
        }
        else {
            count[params.charAt(i)] = count[params.charAt(i)] + 1;
        }
    }
    for (let key in count) {
        if (count[key] === 1) {
            return key;
        }
    }
    return null;
}
console.log(getfirstNonRepeatingCharacterInAString("GeeksfoGeeks"));

function firstNotRepeatingCharacter(s) {
    var strArr = s.split("");
    var found = "_";
    strArr.forEach(function(item, index) {
        if (strArr.indexOf(item) == index && strArr.indexOf(item, index + 1) == -1) {
            if (found === "_") {
                found = item;
            }
        }
    })

    return found;
}

firstNotRepeatingCharacter("abacabad")

Here is another approach:

Everytime you find equal chars store it in an array and break out of the loop. If the char is not found in the array then you have your first nonRepeating char

function nonRepeatingChars(value) {
  const memory = []
  for (let i = 0; i < value.length; i++) {
    for (let j = i + 1; j < value.length; j++) {
      if (value[i] === value[j]) {
        memory.push(value[j])
        break;
      }
    }
    if (!memory.some(x => x === value[i])) {
      return value[i];
    }
  }
  return "all chars have duplicates";
}

console.log('First non repeating char is:',nonRepeatingChars("esen"))
console.log('First non repeating char is:',nonRepeatingChars("esesn"))
console.log('First non repeating char is:',nonRepeatingChars("eseulsn"))
console.log('First non repeating char is:',nonRepeatingChars("esesnn"))

> var firstNonRepeatedCharacter = function (str){   
> for(i=0;i<str.length;i++){
>     if(str.indexOf(str.charAt(i)) === str.lastIndexOf(str.charAt(i))){
>       console.log(str.charAt(i));
>       break;
>     }   } }
> 
> firstNonRepeatedCharacter ("areerak");

you can check below link

https://codepen.io/t3veni/pen/wvvxJzm

Easy way to solve this algorithm, very straight forward.

function firstNonRepeatChar(str){
    let map = {};
    for(let i=0; i<str.length; i++){
        if(Object.keys(map).includes(str[i])){
            map[str[i]]++
        }
        else{
            map[str[i]] = 1;
        }
    }

    for(let j=0; j< Object.values(map).length; j++){
        if(Object.values(map)[j] == 1){
            console.log(Object.keys(map)[j]);
            return
        }
        if (j == Object.values(map).length-1 && Object.values(map)[j] != 1){
            console.log('_');
            return;
        }
        else{
            continue;
        }
    }
}

nonRepeat("aaabbcccdeeef");

Here is one other solution just using array, using 26 unique character as length of array:

var firstUniqChar = (function(s) {
    var arr = [];
    var str = s.toLowerCase();
    for(let c of str){
      let index = c.charCodeAt(0) - "a".charCodeAt(0);
      arr[index]? ++arr[index]: arr[index]=1;
    }
    
    for(let c of str){
      let index = c.charCodeAt(0) - 97;
      if(arr[index] == 1){
        return c;
      };
    }

    return -1;
}("aabcbd"));

console.log(firstUniqChar);

    //To find first non repeating letter 
    //It will check for both upper and lower case
    //only use one String.indexOf()

    var mystr="ohvhvtccggt";
    var checkFirstNonRepeating=function(){
    var ele=[];
      for(var i=0;i<mystr.length;i++) {
      var key=mystr.charAt(i);
      if(!ele[key])
          ele[key]=0;
      ele[key]++;

   //Just check for second occurance of character 
   //no need to use indexOf twice

       if(mystr.indexOf(key,i+1)==-1 && ele[key]<2)  
         return mystr[i];
       }
     return "All repeating letters";
    }
    console.log(checkFirstNonRepeating());
              
        /*
        Input  : "ohvhvtoccggt"
        Output : All repeating letters
        Input  :"oohjtht"
        Output :j 
        */

I used object to keep track of characters count in a string then return the char that has the fa value of 1. Here is a demo:

function firstNotRepeatingCharacter(s) {

// initialize an empty object to store chars

    let seen = {};
    let letter = '';

  // iterate over each char in a string
  // if it is already there increase value by one
  // else set the value to 1

    for(let char of s){
            if (seen[char]){
                    seen[char] +=1;
            } else {
                    seen[char] = 1;
            }
    }

  // iterate over the new constructed object
  // if the value is 1 and the output variable is empty
  // return the associated key to the value 1
  // else return '_'

    for(let v in seen){
        while(seen[v] == 1 && letter === ''){
            letter += v;
            return letter;
        } 
    }
return('_');
}

console.log(firstNotRepeatingCharacter("abacabad"));
console.log(firstNotRepeatingCharacter("cbc"));
console.log(firstNotRepeatingCharacter("bcccccccccccccyb"));
console.log(firstNotRepeatingCharacter("aaa"));

The most satisfactory and easy to understand answer is the following.

function firstNotRepeatingCharacter(s) {
        
    const arr = s.split("");

    for(let i = 0; i < arr.length; i++){
        let chr = arr[i];
        if( arr.indexOf(arr[i]) == arr.lastIndexOf(arr[i])){
            return arr[i]
        }            
    }
    
    return "_"
}

Explanation: It loops through all the characters of a string from forward and backward and then compares the values. If the index of both forward and backward search is true then it returns that character.

let str = 'aabbcdd';
let val = str.split('').reduce((a, e)=>{ if(str.indexOf(e) == str.lastIndexOf(e)) {a = e }; return a})
console.log(val); // c

the implementation below has a good time complexity and it accounts for letters with different cases:

steps must touch every character in the string to know if it's repeated or not

function firstNonRepeatingLetter(wordd) {

    const chars = {}

    let word = wordd.toLowerCase()

    // go through chars
    // store chars in hash with values of array storing index of char and true if only 1 encountered so far
    for (let i = 0; i < word.length; i += 1) {
        let char = word[i]
        if (chars[char]) {
            chars[char][0] = false
        } else {
            chars[char] = [true, i]
        }
    }
    let output = ''
    let index;
    for (let key in chars) {
    // return char with true and lowest index
        if (chars[key][0]) {
            index = index === undefined ? chars[key][1] : index
            if (index >= chars[key][1]) {
                output = key
            }
        }
    }
    return index === undefined ? '' : wordd[index]
}
console.log(firstNonRepeatingLetter('sTreSS')) //T```

The bellow solution is a kind of frequency counter pattern and it will run only one loop, so O(n) will be the time complexity.

function firstNotRepeatingCharacter(str) {
  const obj = {};
  for (let i = 0, L = str.length; i < L; i++) {
    const char = str[i];
    obj[char] = obj[char] ? obj[char] + 1 : 1;
  }

  for (let key of Object.keys(obj)) {
    if (obj[key] == 1) {
      return key;
    }
  }
  return -1;
}

Here is another solution

function firstNotRepeatingCharacter(s) {

     const obj = {};

      for (let i of s) {
        if(!obj[i]) {
            obj[i] = 1;
        } else if (obj[i]) {
            obj[i] = +obj[i] + 1;
        }
      }
    
      for (let [key, value] of Object.entries(obj)) {
        if(value == 1) return key;
      }
    
    return "_"
}