Form a string consisting of the common letters that appear in two input strings

Question

The idea is to write a function that takes two strings and returns a new string that repeats in the previous two: examples:

'ABBA' & 'AOHB' => 'AB'
'cohs' & 'ohba' => 'oh'

A brute force solution would be nested for loops like so:

const x = 'ABCD'
const y = 'AHOB'

function subStr(str1, str2) {
  let final = ''

  for (let i = 0; i < str1.length; i++) {
    for (let j = 0; j < str2.length; j++) {
      if (str1[i] === str2[j]) {
        final += str1[i]
      }
    }
  }

  return final
}



console.log(subStr(x, y)) // => AB

Answer 1

I know the root of all evil is premature optimization, but I would first ask if this is expected to be either a hotspot or usef with large strings.

Because it can be made much more readable using the array methods, but doing so obviously comes with a performance cost. OTOH, your method has its own performance issues.

If this isn’t expected to be particularly performance sensitive, I think that a straightforward method that turned the two strings into arrays then used the filter or map method to generate an array that is then turned into a string would be much more readable, and I prefer readable over performant as long as the performance isn’t a problem.

One additional point, what should your function return for “a”, “aa”? currently it returns “aa”?

Answer 2

One option to simplify the procedure is use Set

const subStr = (a, b) => {
  const set = s => new Set(s);
  const [x, y, s = set([...x, ...y])] = [set(a), set(b)];
      
  for (let z of s) 
    if (!x.has(z) || !y.has(z)) s.delete(z)
    
  return [...s].join('')
}
      
  
console.log(subStr('ABBA', 'AOHB'), subStr('cohs', 'ohba'), subStr('aa', 'a'));

Answer 3

If both string are equal length and sort is allowed, performance can be reduced to linear o(n).

const x = 'ABCD'
const y = 'AHOB'

function subStr(str1, str2) {
  str1 = str1.split('');
  str2 = str2.split('');

  str1.sort();
  str2.sort();

  let final = ''

  for (let i = 0; i < str1.length; i++) {
    if (str1[i] === str2[i]) {
      final += str1[i]
    }
  }

  return final
}



console.log(subStr(x, y)) // => AB