5
\$\begingroup\$

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"));
\$\endgroup\$
  • 2
    \$\begingroup\$ 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. \$\endgroup\$ – RoToRa Apr 4 at 9:17
  • 1
    \$\begingroup\$ 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) \$\endgroup\$ – thadeuszlay Apr 4 at 13:40
3
\$\begingroup\$

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;
}
\$\endgroup\$
  • 1
    \$\begingroup\$ 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/. \$\endgroup\$ – RoToRa Apr 4 at 8:56
  • 1
    \$\begingroup\$ 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? \$\endgroup\$ – RoToRa Apr 4 at 9:16
  • \$\begingroup\$ @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) \$\endgroup\$ – thadeuszlay Apr 4 at 13:37
  • 1
    \$\begingroup\$ 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). \$\endgroup\$ – Mike Brant Apr 4 at 19:26
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – Oh My Goodness Apr 4 at 19:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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