First Unique Character in a String

Question

The task

is taken from leetcode

Given a string, find the first non-repeating character in it and return it's index. If it doesn't exist, return -1.

Examples:

s = "leetcode"

return 0.

s = "loveleetcode",

return 2.

Note: You may assume the string contain only lowercase letters.

My solution

/**
 * @param {string} s
 * @return {number}
 */
function firstUniqChar(s) {
  const arr = Array.from([...s]
                         .reduce((map, x, i) => map.set(x, !isNaN(map.get(x)) ? null : i) , new Map())
                         .values());
  for(let i = 0; i < arr.length; i++) {
    if (arr[i] !== null) { return arr[i]; }
  }
  return -1;
};

Answer 1

• Never indent as you have done. This make code very unreadable due to the long lines.

Map.values() creates an iteratable object. It does not require an array to be created and is \$O(1)\$ storage as it iterates over the already stored values

You have forced the map to be stored as an array. Array.from(map.values()) That means that it must be iterated and stored \$O(n)\$ complexity and storage best case. If you just kept the map and iterated to find the result you could have a best case of \$O(1)\$ to find the result.

Always iterate iteratable objects to reduce memory uses and if there is an early exit to reduce CPU use and complexity.

Rewrite

Is around 2* as fast depending on input

function firstUniqChar(str) {
    const counts = new Map();
    var idx = 0;
    for (const c of str) { // iterate to avoid storing array of characters
        if (counts.has(c)) { counts.get(c).count ++ }
        else { counts.set(c, {idx, count: 1}) }
        idx++;
    }
    for (const c of counts.values()) {
        if (c.count === 1) { return c.idx }
    }
    return - 1;
}

Answer 2

Your solution looks rather map-happy.

It is important to remember for this task that counting higher than 2 of any encountered letter is needless processing as is any processing on any letter after the earliest positioned unique letter.

Also, doing a complete sweep of the input string may be ill-advised if the input string is of considerable length.

Due to not being as well across .js as others here are, I'll post a humble for loop.

function firstNonRepeatedCharacterPosition(string) {
    for (let char, pos, i = 0; i < string.length; ++i) {
        char = string.charAt(i);
        pos = string.indexOf(char);
        if (pos == i && string.indexOf(char, i + 1) == -1) {
            return pos;
        } 
    }
    return -1;
}

console.log(firstNonRepeatedCharacterPosition('abcbebc'));

It does make 3 function calls per iteration, but they aren't heavy ones, there is at most only one pass through the string, and early-return programming is in effect.

• Grab the letter at the incremented position.
• Find the earliest occurrence of that letter.
• Check if there is a later occurrence of the same letter.

The later the unique letter exists (or if there are no unique letters), the more laborious my function is. On the other hand, if the first letter is unique, then you are finished in just 3 function calls.

p.s. I lack the knowledge to interpret your js code, so I cannot review it beyond saying that it isn't very novice friendly.

---

After Rotora's challenge, I was doubting myself, so I whacked this little battery of tests together:

function MickMacKusa(string) {
    for (let char, pos, i = 0; i < string.length; ++i) {
        char = string.charAt(i);
        pos = string.indexOf(char);
        if (pos == i && string.indexOf(char, i + 1) == -1) {
            return pos;
        } 
    }
    return -1;
}

function RoToRa(string) {
    for (let char, pos, i = 0; i < string.length; ++i) {
        char = string.charAt(i);
        if (string.indexOf(char, i + 1) == -1) {
            return i;
        } 
    }
    return -1;
}

let table = document.getElementById("test"),
    row;
for (let i = 1; i < table.rows.length; ++i) {
    row = table.rows[i];
    row.cells[3].innerHTML = MickMacKusa(row.cells[0].innerHTML);
    row.cells[4].innerHTML = RoToRa(row.cells[0].innerHTML);
}

<table id="test" border="1" cellpadding="4">
<tr><th>Input</th><th>Letter</th><th>Index</th><th>MickMacKusa</th><th>RoTora</th></tr>
<tr><td>abccbcba</td>  <td>-</td> <td>-1</td> <td></td> <td></td></tr>
<tr><td>abcbebc</td>   <td>a</td> <td> 0</td> <td></td> <td></td></tr>
<tr><td>abc</td>       <td>a</td> <td> 0</td> <td></td> <td></td></tr>
<tr><td>aabbc</td>     <td>c</td> <td> 4</td> <td></td> <td></td></tr>
<tr><td>abcba</td>     <td>c</td> <td> 2</td> <td></td> <td></td></tr>
<tr><td>abba</td>      <td>-</td> <td>-1</td> <td></td> <td></td></tr>
<tr><td>abaa</td>      <td>b</td> <td> 1</td> <td></td> <td></td></tr>
<tr><td>aabcbcbca</td> <td>-</td> <td>-1</td> <td></td> <td></td></tr>
</table>