0
\$\begingroup\$

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

\$\endgroup\$
2
  • 5
    \$\begingroup\$ Could you clarify, with additional examples, what should happen when letters appear in different orders within the two input strings? \$\endgroup\$ Dec 26 '18 at 5:41
  • \$\begingroup\$ 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") \$\endgroup\$
    – Curtis F
    Jun 2 '19 at 2:13
1
\$\begingroup\$

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

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

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

\$\endgroup\$
1
\$\begingroup\$

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

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

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.