0
\$\begingroup\$

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;

}
\$\endgroup\$
4
  • \$\begingroup\$ Is the second string guaranteed to not have repeated chars? What is expected behaviour otherwise? \$\endgroup\$
    – juvian
    Apr 3 '18 at 18:28
  • \$\begingroup\$ 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'. \$\endgroup\$ Apr 3 '18 at 18:50
  • \$\begingroup\$ I just revised the code to accommodate the edge case mentioned above. \$\endgroup\$ Apr 3 '18 at 19:20
  • \$\begingroup\$ 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" \$\endgroup\$
    – juvian
    Apr 3 '18 at 19:30
1
\$\begingroup\$

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")

\$\endgroup\$
0

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.