Return the first recurring character in a string

Question

The task:

Given a string, return the first recurring character in it, or null if there is no recurring character.

For example, given the string "acbbac", return "b". Given the string "abcdef", return null.

My imperative solution:

function getFirstRecurringChar(str) {
 let i = 0;
 const len = str.length;
 const letters = {};
 while(i < len && !letters[str[i]]) { letters[str[i++]] = true; }
 return i < len ? str[i] : null;
};
console.log(getFirstRecurringChar("acbbac"));

My functional solution:

const getFirstRecurringChar2 = str => {
 const letters = {};
 let lastLetter;
 return Array.from(str).some(x => {
 if(letters[x]) {
 lastLetter = x;
 return true;
 }
 letters[x] = true;
 return false;
 }) ? lastLetter : null;
};
console.log(getFirstRecurringChar2("abcdef"));

• RoToRa: The requirement "first recurring character" isn't clear. In your example acbbac the answer could also be "a", because it's the first character that recurs.
• thadeuszlay: As I mentioned in an earlier comment: I think it's the character that reoccurs first. (at least I solved it like this and it would be consistent with the given example in the task description)

Answer 1

The problem is similar to your other "two of something" problems, such as Palindrome and Find the elements that appear only once. As in those problems, a Set is the appropriate data structure.

The main difference is that early exit is possible (when two of something is found) so we'd rather not be inside of a reduce.

const firstRepeated = s => {
 const seen=new Set();
 for (var c of s) {
 if (seen.has(c)) return c; 
 else seen.add(c); 
 }
 return null;
}

• RoToRa: Your regular expression doesn't match the original requirement. It only matches duplicate characters that immediately follow each other (e.g. bb) but not ones with other characters in between (e.g. bxb). It should be /(.).*1円/.
• RoToRa: I just realized, that my regexp won't work like expected either. I think the requirement is not clear. What is the "first" recurring character? Is the the first character that recurs or the character who's recurrence is first?
• thadeuszlay: @RoToRa I think it's the latter. (at least I solved it like this and it would be consistent with the given example in the task description)
• Mike Brant: Though Set is a very useful construct and I like this solution from a code readability standpoint, it is worth pointing out that is would likely not perform as well as map type of approach as used in original solutions, if that is what matters most (like you need to process REALLY long strings).
• Oh My Goodness: @MikeBrant note also that strings can't be longer than character set without having a duplicate (and exiting early). Unicode has under 300k assigned code points. ASCII and Latin-1 of course have far fewer.