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

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

• Could you clarify, with additional examples, what should happen when letters appear in different orders within the two input strings? Dec 26 '18 at 5:41
• How is this supposed to behave with repeated characters? For example, your subStr function returns "ABBA" on the input ("ABBA", "AOHB"), which isn't the output you specified ("AB") Jun 2 '19 at 2:13

## 3 Answers

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”?

• That would make a nice one-liner: common = (str1, str2) => str1.split('').filter(s => str2.contains(s)).join('') Dec 28 '18 at 9:30

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'));

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

• What exactly do you mean with $n$, and how can sorting be $\mathcal O(n)$? Jun 2 '19 at 9:10