First non-repeating character in string

Question

I've been trying to learn a bit of JavaScript over the last few weeks, and inspired by this current hot network question, I tried creating a function for finding the first non-repeating character in a string. Is my approach a decent one, and is there any obvious improvements which can be made?

function firstNonRepeatingCharacter(inData) {
  var dict = {};
  var key;
  
  for (var i = 0; i < inData.length; i++) {
    key = inData.charAt(i);
    if (key in dict) {
      dict[key] += 1;
    } else {
      dict[key] = 1;
    }
    
  }
  
  for (var v in dict) {
    if (dict[v] === 1) {
      return v;
    }
  }
  
  return undefined;
}

console.log(firstNonRepeatingCharacter("axxyzz"))

Answer 1

Define the task

I am assuming the task is to find first single instance of a character in the string as this is what the code does. "Repeating" could imply sequential instances of an item.

When defining coding tasks always try to avoid any possible ambiguity.

Code style

General points regarding code style.

• The variable dict and key can be constants.

• There is no need to ever add undefined to a return. The default return is undefined thus return undefined and return are identical.

• Functions return automatically. Unless you have something to return there is no need to add a return to the last line of your function.

• When using var to declare variables do so at the top of the function. Eg the var i in the for loop should be declared at the top of the function or use let i

• JavaScript String are array like and can be indexed using bracket notation (strings are immutable thus its read only). eg key = inData.charAt(i) is the same as key = inData[i]

• JavaScript String are also iterable Iteration_protocols thus you can test each character using for(const key of inData) rather than the for;; and then indexing the character.

• Naming is rather poor. Avoid, when possible, naming variables by type or usage pattern, name them for what they contain.

  Some name change suggestions...

  • dict could be charCounts
  • inData could be text, str or string
  • key better as char, letter, or character

Rewrite

A general rewrite using the points above.

Note that using for (const char of str) { makes the rewrite ~2% slower than your original code.

function firstNonRepeat(str) {
  const counts = {};  
  for (const char of str) {
    if (char in counts) { counts[char] += 1 }
    else { counts[char] = 1 }    
  }  
  for (const char in counts) {
    if (counts[char] === 1) { return char }
  }
}

Performance

End users are the ultimate judges of our code, they are also the ones that pay the bills. End users when asked to rate two identical applications the more performant app is always rated as the better product.

Your code has some performance anti-styles and that is why I have added a performance review and rewrites. Though that said your code's time and space complexity is as good as it can be \$O(n)\$

Specifically performance points are string handling, and how you use a dictionary (hash map)

This task is at best \$O(n)\$ (time and space) and as you have achieved this any performance gain will be under an order of magnitude.

Performance should not be a coding after thought, performance code should be your default style.

Performance tips

• In JS Number are much quicker than String (even single characters)

• We can use String.charCodeAt` to handle a character as a number.

• With the character as a number the character dictionary can be replaced with an array. Even though the array will be a sparse array, indexing a sparse array is quicker than indexing an Object (even if the indexing is via Numbers).

• To track the first occurrence we don't need to count any characters that occurred more than once.

  We can use a Set to hold character codes when we first see a character, if we see the character a second time we delete it Set.delete from set of once only characters. If we see a character a 3rd or more times we ignore it. This lets us avoid many of the expensive hashing function calls required when accessing the set.

  Using a Set that contains only single occurrences also means that we don't need to iterate the dictionary to find the character with a count 1, we know that the first item in the dictionary (Set) is the one we want. Thus we can return the character that is represented by the first character code in that set.

  EG assuming that once has items return String.fromCharCode(once.values().next())

  Using iterator Set.values and String.fromCharCode

Generally any of these changes will have very little effect when the input string in only a dozen or two characters long, but over 100 characters and the gain is a worth while three fold increase in throughput (Something end users will notice)

Performance rewrites

There are two rewrites addressing performance

• The first uses a more idiomatic style.

• The second is a totally performance oriented style

Idiomatic performance style

function firstNonRepeat(str) {
    const counts = [], once = new Set();
    for (let i = 0; i < str.length; i++) {
        const code = str.charCodeAt(i);
        if (counts[code] === 1) {
            counts[code] = 2;
            once.delete(code);
        } else if (!counts[code]) {
            counts[code] = 1;
            once.add(code);
        }
    }
    return once.size > 0 ? 
        String.fromCharCode(once.values().next().value) : 
        undefined;
}

Performance style

This style gains about 3-5% over the above rewrite across all input string sizes.

I have added comments to explain why code is different than above.

Note that the for (; i < str.length;) is not faster than for (i; i < str.length; i++) but is just a compact source style to aid readability. I would normally use a while loop (eg while(i < LEN) {) but recent changes (Chrome) have impacted the relative performance of for and while loops to favor for loops.

function firstNonRepeat(str) {
    const counts = [], once = new Set(), ONE = 1, TWO = 2;
    var i = 0;
    for (; i < str.length ;) {       // avoids the block scope overhead generated when using let.
        const code = str.charCodeAt(i++);
        const count = counts[code]; // to reduce the number of times we index the sparse array
        if (count === ONE) {        // local scoped Constants are quicker than literals
            counts[code] = TWO;     // local scoped Constant
            once.delete(code);
        } else if (count === undefined) {  // to avoid the type coercion that !count has
            counts[code] = ONE;     // local scoped Constant
            once.add(code);
        }
    }

    // To return the first item when it is not known if there are any entries
    // the following has the advantage over testing size and using .next().value
    // And I find the line below cleaner than the return in previous example.
    for (const code of once) { return String.fromCharCode(code) }
}

Answer 2

that's my post! I'm glad you were inspired by it.

As far as logic goes, this is a great and quite commonly agreed upon way to solve the problem in O(n) time, as long as the language you write it in maintains the order of insertion of a dictionary(which JS does). Well done.