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

• I.Am.A.Guy: this looks like a good solution, but is there any way we could leverage the constraint "string contains only lowercase letters" to our advantage?
• Blindman67: @I.Am.A.Guy JS has unicode Strings and upper and lowercase characters are spread throughout the character set not just [a-z]
• I.Am.A.Guy: Interesting! However, in the case that it's just a-z, we could check if map length exceeds 26. Depends on how much overhead it would be though. I'm thinking not much if we put it in the else clause. What do you think?

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>

• RoToRa: I haven't tried it out, but I think you don't need to use indexOf twice. Just if (string.indexOf(char, i + 1) == -1) { would do.
• mickmackusa: As i gets closer to the tail end, there will be a greater chance that the duplicate letter will be "behind" (left of) i rather than "in front" (to the right of it). Consider the third b in my sample. It is not a unique letter, but would be considered one because there are no bs to the right to find.
• RoToRa: But there never can be a duplicate "behind" i, because they have already been tested.
• mickmackusa: On abcbebc, when i = 5 and char = 'b', looking for the next b from i + 1 will return -1, but that character is not unique. I could be wrong, I'll consider your advice.
• mickmackusa: @RoTora I've included a runnable test script in my answer. If I have misunderstood your recommendation, please clarify.