Verifying if a string can be created with the letters of another string

Question

This is basically based on the following question on stackoverflow which was based on a codewars assignment that can be found here

Problem statement

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

My solution

function scramble(str1, str2) {
  if (str1.length < str2.length) {
    return false;
  }
  const set = new Set([...str2]);
  return Array.from( set ).every( letter => str2.split(letter).length <= str1.split(letter).length );
}

As with the original question on SO, my question would be if there are more efficient ways of completing the assignment. I am mainly worried about the string.split, but I didn't know of any other method that might be faster (I know I should substract 1 to get the actual letter count, but it doesn't matter for this usecase)

Answer 1

Counting with str2.split(letter).length takes linear time on the size of the string, so it’s not efficient to repeat it for each distinct character in the input (even if that still results in a linear overall runtime, strictly speaking, since Unicode is limited in size). Here’s an accurate implementation of the solution Mike Brant described, since your rewrite that creates a map still does the slow count:

const getCounts = iterable => {
    const result = new Map();

    for (const x of iterable) {
        result.set(x, (result.get(x) ?? 0) + 1);
    }

    return result;
};

const scramble = (available, target) => {
    const remaining = getCounts(available);

    for (const c of target) {
        const count = remaining.get(c);

        if (!count) {
            return false;
        }

        remaining.set(c, count - 1);
    }

    return true;
};

An alternative solution with decent performance is to compare sorted versions of the strings:

const scrambleSorted = (available, target) => {
    let i = -1;

    for (const c of target) {
        i = available.indexOf(c, i + 1);

        if (i === -1) {
            return false;
        }
    }

    return true;
};

const scramble = (available, target) =>
    scrambleSorted([...available].sort(), [...target].sort());

(This would be the one with constant auxiliary space if you were allowed to mutate the input, but JavaScript doesn’t have mutable strings.)

Also, note that strings are iterables of codepoints, but string functions like split, which predate iterables, operate on UTF-16 code units. So anything that mixes iteration (e.g. new Set(str), [...s], Array.from(s), for (c of s)) won’t work with split-based counting.

---

Or, when the number of distinct characters is small and even contiguous, you can use an array:

const scramble = (available, target) => {
    if (target.length > available.length) {
        return false;
    }

    const remaining = Array(26).fill(0);

    for (let i = 0; i < available.length; i++) {
        const c = available.charCodeAt(i) - 97;
        remaining[c]++;
    }

    for (let i = 0; i < target.length; i++) {
        const c = target.charCodeAt(i) - 97;

        if (--remaining[c] === -1) {
            return false;
        }
    }

    return true;
};

Answer 2

Your logic seems hard to follow. Why spread str2 to array, which you then read into a Set, only to turn around and make the Set into an array, which you then iterate, comparing each letter’s count in each string by splitting them repeatedly?

You see how long and convoluted that sentence was? The last line of code there is kind of the same, dense and hard to follow.

The problem should be solved by counting characters for str1 into map keyed by each letter. You then iterate through str2 and decrement those counters. If any counter goes to -1 you have false condition. This approach means each letter in passed string only needs to be visited once making performance linear to the combined length of the strings in operational complexity. Your current solution has exponential complexity.

Answer 3

From a short review;

• Whenever I deal with search algorithms, I like to use haystack and needle as variable names, they are more evocative then str1 and str2

• There are no comments, I think you need to comment why you do const set = new Set([...str2]); The rest of the code is obvious once the reader figures that one out

• For the counting part, there are really 3 strategies;

  • use String.split() Fast, uses memory though
  • use String.match() Fast, uses more memory though
  • use String.indexOf() Somehow slow nowadays, least memory

  So I think your approach is fine. More research here.

This is a counter proposal with the above in mind;

function scramble(haystack, needle) {
  if (haystack.length < needle.length) {
    return false;
  }
  //"Hello World" -> Set('H', 'e', 'l','o','w','r','d')
  const uniqueCharacters = new Set([...needle]);
  return Array.from(uniqueCharacters).every(c => occurrences(needle,c) <= occurrences(haystack, c));
}

function occurrences(haystack, needle){
  return haystack.split(needle).length - 1;
}

Answer 4

You don't need to convert the string to an array before passing it to a set. The Set constructor can take any iterable as an argument. So, you can directly pass the string to get all the unique characters:

const set = new Set(str2)

In the code, you are converting a string to an array to a set to an array again. Even, inside the every callback you are doing split on both strings. Which means, you need to search through both strings set.size times, create an array and compare their length.

You can write it in such a way that str1 is looped only once and str2 is looped until it fails your condition.

• You can create a counter function which maps each character with the number of times it occurs in a string. Call the function on str1
• Loop through the second string and return false if
  • the counter doesn't have that character.
  • the value becomes negative once you account for the current character.
• If the loop is completed, the string can be scrambled.

function counter(str) {
  const counter = {};
  for (const c of str)
    counter[c] = counter[c] + 1 || 1;
  return counter
}

function scramble(str1, str2) {
  if (str1.length < str2.length)
    return false;

  const count = counter(str1);

  for (const c of str2) {
    if (!count.hasOwnProperty(c) || --count[c] < 0)
      return false
  }
  
  return true
}

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

Answer 5

Well, the answer by Mike Brant indicated partly what was wrong with my original approach, as in iterating str2 potentially 2 times (if all characters would have been unique).

I still don't think I have to map each letter by key for str1, in fact I see str1 as pretty much irrelevant, and only for verifying if a letter occurs at least as many times as it does in str2.

So, to make it less compact but only iterate str2 once, I went for the following solution

function scramble(str1, str2) {
  if (str1.length < str2.length) {
    return false;
  }
  const set = new Set();
  let c;
  for (let i = str2.length; i--;) {
    c = str2.charAt(i);
    if (set.has(c)) {
      continue;
    }
    if ( str2.split(c).length > str1.split(c).length) {
      return false;
    }
    set.add(c);
  }
  return true;
}

And if I make a map of str1 first, I went for the following solution

function createMap(str) {
  let result = {};
  let c;
  for (let i = str.length; i--;) {
    c = str.charAt(i);
    result[c] = (result[c] || 0) + 1;
  }
  return result;
}

function scramble(str1, str2) {
  if (str1.length < str2.length) {
    return false;
  }
  const set = new Set();
  const map = createMap(str1);
  let c;
  for (let i = str2.length; i--;) {
    c = str2.charAt(i);
    if (set.has(c)) {
      continue;
    }
    if (!map[c] || str2.split(c).length - 1 > map[c]) {
      return false;
    }
    set.add(c);
  }
  return true;
}

Both solutions are in the same ballpark when it comes to performance

Answer 6

I think you don't need the splits. Also, I would put the subset check in a separate function.

function scramble(str1, str2) {
  const set1 = new Set([...str1]);
  const set2 = new Set([...str2]);
  return isSubset(set2, set1);
}

function isSubset(a, b) {
  return Array.from(a).every(x => b.has(x));
}

Answer 7

Could this one-liner do the job? I hope I am not missing anything.

function scramble(str1,str2) {
return [...str2].every(e=> str2.split(e).length <= str1.split(e).length);
}

// ---- Test ---

console.log(scramble('rkqodlw', 'world'));               // true
console.log(scramble('cedewaraaossoqqyt', 'codewars'));  // true
console.log(scramble('katas', 'steak'));                 // false
console.log(scramble('myworld', 'mmy'));                 // flase because only 1 m (need 2 m's)