Reorder the letters of one string to match the order of letters in a second string I have a solution to the following problem that I'd like to know if there's a way I could decrease runtime complexity for.

The directions are: reorder the letters of the first string to match the order of the letters in the second string. If a letter in the first string is not present in the second string, add it to the end of the reordering.

Example input: 'shouts', 'soup'
Example output: 'ssouht'

My code is as follows: 

const reOrderLetters = (string1,string2) =&gt; {
  let tailString = '';
  let newString = '';
  const mapped = {};

  for (let i=0;i&lt;string1.length;i++) {
    let char = string1[i];
    if (string2.indexOf(char) !== -1) {
      if (!mapped[char]) {
        mapped[char] = char;
      } else {
        mapped[char] = mapped[char] += char;
      }
    } else {
      tailString += char;
    }
  }
  for (let i=0;i&lt;string2.length;i++) {
    let char = string2[i];
    if (mapped[char]) {
      if (mapped[char].length &gt; 1 &amp;&amp; string2.slice(i+1).indexOf(char) !== -1) {
        newString += mapped[char].slice(mapped[char].length-1);
        mapped[char] = mapped[char].slice(0,mapped[char].length-1);
      } else {
        newString += mapped[char];
      }
    }
  }
  return newString += tailString;

}
Your code is pretty good, except for using indexOf(char), as that can be quite expensive: O(string2.length). Here is how I would do it to avoid using that. Assuming hashmap access is O(1) and n being the max length between both strings, my implementation runs in O(n)



function characterCount (str) {
  var chars = {};
  
  for (var i = 0; i &lt; str.length; i ++) {
    chars[str[i]] = (chars[str[i]] || 0) + 1;
  }
  
  return chars;
}



function reOrderLetters (str1, str2) {
  var count1 = characterCount(str1); // O(n)
  var count2 = characterCount(str2); // O(n)
  var result = [];
  var seenCount = {}
  
  for (var i = 0; i &lt; str2.length; i++) {
    var char = str2[i];
    seenCount[char] = (seenCount[char] || 0) + 1; 
    
    if (count1.hasOwnProperty(char)) {
      var remaining = count1[char] % count2[char];
      var toRepeat = Math.floor(count1[char] / count2[char]);
     
      if (seenCount[char] &lt;= remaining) {
        toRepeat = Math.ceil(count1[char] / count2[char]);      
      }
      
      result.push(char.repeat(toRepeat)); 
    } 
  }
  
  for (var i = 0; i &lt; str1.length; i++) {
    var char = str1[i];
    
    if (count2.hasOwnProperty(char) == false) {
      result.push(char.repeat(count1[char]));
      count2[char] = true;
    }
  }
  
  return result.join("");
}


console.log(reOrderLetters("shouts", "soups") == "sousht")
console.log(reOrderLetters("aa", "aaaa") == "aa")
console.log(reOrderLetters("aabbbba", "abab") == "aabbabb")