Optimizing determining whether a subset of a string can be rearranged to form another string

user_13714287 0
Viewed 104

Complete the function scramble(str1, str2) that returns true if a portion of str1 characters can be rearranged to match str2, otherwise returns false.

Notes:

  • Only lower case letters will be used (a-z). No punctuation or digits will be included.
  • Performance needs to be considered
  • Input strings s1 and s2 are null terminated.

Examples

'rkqodlw', 'world' ==> True
'katas', 'steak' ==> False

My Code:

function scramble(str1, str2) {
  let str = '';

  for (i = 0; i < str2.length; i++) {
    if (str1.includes(str2[i])) {
      str1 = str1.replace(str2[i], '')
      str += str2[i]
    }
    if (str === str2) return true
  }
  return false
}
algorithm javascript
2 Answers

If the strings are so unreasonably huge that runtime really is an issue, you can group one of the strings into an object first, so that the overall complexity is O(n) instead of O(n ^ 2):

function scramble(str1, str2) {
  const grouped = {};
  for (const char of str1) {
    grouped[char] = (grouped[char] || 0) + 1;
  }
  for (const char of str2) {
    if (!grouped[char]) return false;
    grouped[char]--;
  }
  return true;
}

console.log(scramble('rkqodlw', 'world'));
console.log(scramble('katas', 'steak'));

user_95152070

You can do this in linear time by making a frequency counter for each word. If, for every unique character in str2, you find that its count of letters is <= the count for that character in str1, then return true because str1 has some subset of characters that could form str2.

Code:

const frequencyCount = s => [...s].reduce((a, e) => {
  a[e] = ++a[e] || 1;
  return a;
}, {});
  
const scramble = (a, b) => {
  const aFreq = frequencyCount(a);  
  return Object.entries(frequencyCount(b)).every(([e, count]) =>
    count <= aFreq[e] 
  );
};

console.log(scramble("rkqodlw", "world"));
console.log(scramble("katas", "steak"));

user_62433520
Related