I am trying to solve the CodeWars kata Scramblies:

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.

Examples

scramble('rkqodlw', 'world') ==> True
scramble('cedewaraaossoqqyt', 'codewars') ==> True
scramble('katas', 'steak') ==> False

My code doesn't pass all the tests in this kata. Apparently it fails when str2 repeats a letter that is not in str1.

For example, this is one of the errors:

Incorrect answer for inputs:

s1='scriptjavx'
s2='javascript'

: expected true to equal false

Here's my solution

function scramble(str1, str2) {
  let sameChar = ""
  for (char of str2) {
    if (str1.includes(char)) {
      sameChar  = char
    }
  }
  if (str2 == sameChar) 
    return true
  else
    return false;
}

Can you tell me how I could fix it?

CodePudding user response：

The problem is that str1.includes(char) still allows the found character to be found again at the same spot. For example, if str2 is "aa" and str1 is "a" you can see how that goes wrong. That single "a" in str1 should only serve once for a match, not twice.

A solution is to maintain a count per character:

function scramble(str1, str2) {
  if (str2.length > str1.length) return false;
  const counts = {};
  for (let c of str1) {
    counts[c] = (counts[c] || 0)   1
  }
  for (let c of str2) {
    if (!counts[c]) return false;
    counts[c]--;
  }
  return true;
}

CodePudding user response：

You made great logic but you need to test it both ways, you only tested on str2, I added your same test on str1

function scramble(str1, str2) {
  let sameChar1 = ""
  let sameChar2 = ""
  for (char of str1) {
    if (str2.includes(char)) {
      sameChar1  = char
    }
  }
  for (char of str2) {
    if (str1.includes(char)) {
      sameChar2  = char
    }
  }
  if (str1 == sameChar1 && str2 == sameChar2) 
    return true
  else
    return false;
}
console.log(scramble('scriptjavx', 'javascript'))

CodePudding user response：

You could create a copy for str1 and remove each matched character, so that it can not be matched multiple times, like this:

function scramble(str1, str2) {
  let sameChar = ""
  let str1Copy = [ ...str1 ];
  
  for (const char of str2) {
    const idx = str1Copy.indexOf(char);
    if (idx !== -1) {
      str1Copy.splice(idx, 1);
      sameChar  = char;
    }
    else {
      break;
    }
  }
  
  return str2 == sameChar;
}

console.log(scramble("scriptjavx", "javascript"));  // false
console.log(scramble("scriptjavxa", "javascript")); // true