-2
\$\begingroup\$

Given a string, write a program to find the first non repeated character in the string. Assume that the given string only contains ASCII chars. Examples can be found in the test cases below.

code.js

'use strict';
module.exports = input => {
    if (typeof input !== 'string') {
        throw new TypeError(`Expected a string, got ${typeof input}`);
    }
    if (input.length === 1) {
        return input;
    }
    const map = Object.create(null);
    for (let char of input) {
        let count = map[char];
        if (count) {
            count += 1;
        } else {
            count = 1;
        }
        map[char] = count;
    }

    for (let char of input) {
        const count = map[char];
        if (count === 1) {
            return char;
        }
    }
    return '';
};

test.js

import test from 'ava';
import fn from '.';

test('input should be string', t => {
    const err = t.throws(() => fn(123), TypeError);
    t.is(err.message, 'Expected a string, got number');
});

test('single char string should return as it is', t => {
    t.is(fn('a'), 'a');
});

test('should find the first non repeated char', t => {
    t.is(fn('total'), 'o');
    t.is(fn('fffff'), '');
});
\$\endgroup\$
6
  • \$\begingroup\$ Isn't using a map overkill? Wouldn't it be enough to store the previously inspected character and compare with the current one? \$\endgroup\$ Mar 22, 2017 at 15:56
  • \$\begingroup\$ My solution runs in linear time. \$\endgroup\$
    – CodeYogi
    Mar 22, 2017 at 15:58
  • 2
    \$\begingroup\$ But you have to fill the map 1st, to check the result. You maybe should elaborate of all your goals and requirements in your question. As is, it's just a code dump. \$\endgroup\$ Mar 22, 2017 at 16:00
  • \$\begingroup\$ Can you see the test cases? they more than enough to understand the intent. \$\endgroup\$
    – CodeYogi
    Mar 23, 2017 at 1:49
  • \$\begingroup\$ Guys, please be mindful while down voting the question. \$\endgroup\$
    – CodeYogi
    Apr 8, 2017 at 6:21

3 Answers 3

4
\$\begingroup\$

You might consider iterating the map in the second part of your code vs. iterating the string again.

Why? Depending on the expected alphabet of characters and the expected length of the input string, it might be faster to iterate the map than the input string.

For example, if you know you are dealing with an alphabet of 256 characters but you might have input strings lengths into the thousands or tens of thousands of characters, it would be quicker to iterate the map.

This would require a change to your map so as to store the first index where a character is encountered in the string, so you might build a data structure like:

{
    'a': {
        'count': *
        'index': *
    },
    ...
}

So when writing the map, that may look like:

let inputLength = input.length;
for (let i = 0; i < inputLength; i++ ) {
    let char = input.charAt(i);
    if(char in map) {
        map[char].count++;
    } else {
        map[char] = { count: 1, index: i };
    }
}

And when iterating the map after writing the string to it, you would need to iterate the entire map like:

let lowestIndex = inputLength;
for(char in map) {
    if(map.char.count === 1 && map.char.index < lowestIndex) {
        lowestIndex = map.char.index;
    }
}
// note we relay on `charAt()` behavior here which returns empty string
// if index is out of range (i.e. the for loop above did not change value of
// lowestIndex)
return input.charAt(lowestIndex);

You have some cases where you seem to unnecessarily create new variables. Some examples follow:

There is no need for count here:

for (let char of input) {
    let count = map[char];
    if (count) {
        count += 1;
    } else {
        count = 1;
    }
    map[char] = count;
}

This could be:

for (let char of input) {
    if(char in map) {
        map[char]++;
    } else {
        map[char] = 1;
    }
}

There is no need for count here either:

for (let char of input) {
    const count = map[char];
    if (count === 1) {
        return char;
    }
}

This could be:

for (let char of input) {
    if (map[char] === 1) return char;
}
\$\endgroup\$
0
\$\begingroup\$

Using a map is not safe, there is no guarantee that you will enumrate the map in the order characters where added. In other words, your string might be dcba but your map might be ordered as abcd.

I would try something simple like:

for (let i in input) {
  let char = input[i];
  if (input.indexOf(char, i+1) < 0)
    return char;
}
return '';
\$\endgroup\$
4
  • \$\begingroup\$ I think that is why the second part of the code iterates the string again to compare against the map :) \$\endgroup\$
    – Mike Brant
    Mar 22, 2017 at 19:10
  • 1
    \$\begingroup\$ This is also a (slightly optimized) O(n^2) solution as every time you are iterating the input string both in the for loop and during the indexOf() operation. \$\endgroup\$
    – Mike Brant
    Mar 22, 2017 at 19:27
  • \$\begingroup\$ You're right that I had missed that the OP iterated the string and not the map in the second loop and that my method had a higher order but maintaining a hash is quite expensive compared to the built in 'indexOf', at least in a contrived test using indexOf ran two to four times faster than the OP's version. Of course as you pointed out it would probably perform better on longer strings though the limited English character set would make this an unlikely candidate for long strings. \$\endgroup\$ Mar 23, 2017 at 1:38
  • \$\begingroup\$ this is a good point regarding testing the approaches against your expected input use cases. Your proposed solution would actually perform VERY well for strings like natural language words where there is not highly repetitive characters in the typical input string. I was looking at this more as programming challenge or interview question based on the question tags, where one might consider a theoretically linear complexity solution better than an exponential one. \$\endgroup\$
    – Mike Brant
    Mar 23, 2017 at 2:48
0
\$\begingroup\$

There may be an easier way to do this. Try looking at something along the lines of:

function firstNoRepeat(input){
  if(typeof input !== 'string'){
    throw new Error('First argument value must be a string.')
  }
  for(let char of input){
    if(input.indexOf(char) === input.lastIndexOf(char)){
      return char
    }
  }
  return 'String does not contain any non-repeating characters.'
}

Any repeated character will return differing output values for indexOf() and lastIndexOf(). So if you come to a character where these two values end up being equal, it tells you that the character only appears once. By iterating over the input string's characters from left to right and returning the very first character that passes the index matching test, you ensure that the first unique character in the string is the one that gets returned.

Obviously, if you iterate over the entire string and no character passes the test, it means every character in the string repeated at least once; which is why the final string return value at the end of the function is included, but will only ever be reached and returned if the input is composed completely of non-unique characters.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.