# 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) => {
let tailString = '';
let newString = '';
const mapped = {};

for (let i=0;i<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<string2.length;i++) {
let char = string2[i];
if (mapped[char]) {
if (mapped[char].length > 1 && 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;

}

• Is the second string guaranteed to not have repeated chars? What is expected behaviour otherwise? Commented Apr 3, 2018 at 18:28
• Good question. That's an edge case I didn't think about. It's a question I found on Glassdoor interviews, so though I don't know, for the purpose of this exercise, let's say that if the second string has repeated chars that are present in the first string, that they be split up. So if the above input were instead: 'shouts', 'soups', expected output would be: 'sousht'. Commented Apr 3, 2018 at 18:50
• I just revised the code to accommodate the edge case mentioned above. Commented Apr 3, 2018 at 19:20
• If by split you mean distribute the amount of characters in string1 on the positions of that char over string2, your code produces incorrect output for example on "aa", "aaaa" Commented Apr 3, 2018 at 19:30

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 < 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 < 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] <= remaining) {
toRepeat = Math.ceil(count1[char] / count2[char]);
}

result.push(char.repeat(toRepeat));
}
}

for (var i = 0; i < 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")