6
\$\begingroup\$

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)

\$\endgroup\$
1
\$\begingroup\$

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;
};
\$\endgroup\$
  • \$\begingroup\$ Could it be you ment || instead of ??? The runtime on the test themselves don't make such a huge difference, you stay in the same ballpark, but since the map would have at most 26 characters, I guess it doesn't make such a huge difference? The second one sadly enough fails, but I think that's mainly because you sort the large strings \$\endgroup\$ – Icepickle Jul 30 at 17:22
  • \$\begingroup\$ @Icepickle: ?? is a somewhat new operator. You can substitute || in this specific case if targeting an engine that doesn’t support it. \$\endgroup\$ – Ry- Jul 30 at 17:27
  • 1
    \$\begingroup\$ @Icepickle: Oh, I did miss that there were new criteria. (Came here from the SO question.) If it’s just lowercase ASCII, then yes, traversing the string 26 times isn’t a huge constant factor. \$\endgroup\$ – Ry- Jul 30 at 17:31
  • \$\begingroup\$ Yeah, the engine itself seems to be node v8 so since it's only available since node 14 I guess that is reasonable :D I thought on the SO question there were no requirements whatsoever, I just thought I would create a question based on that once because it was just a fun challenge (and based on the answers, it seems others might have agreed) \$\endgroup\$ – Icepickle Jul 30 at 17:31
  • \$\begingroup\$ It was a hard choice to make between this answer and the one from agida, but I think this one fits more with my intention of the question :) \$\endgroup\$ – Icepickle Jul 31 at 7:56
5
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ The set ensure that I only have the unique characters of str2 so I don't have to search the same characters twice. Based on your answer I self answered my question with a faster algorithm (both with testing map & string.split as they seem to be equally matched for speed at that time) \$\endgroup\$ – Icepickle Jul 30 at 7:33
  • 2
    \$\begingroup\$ Minor fix: the current solution is O(distinct chars × length), so quadratic in a sense but not exponential. \$\endgroup\$ – Ry- Jul 30 at 17:33
5
\$\begingroup\$

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;
}
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Thanks, I think it looks good. I agree with the naming, but I just left it as it was as it was part of the challenge, you are right that it makes more sense to give them a good name :) I did create a self answer based on Mike Brandts answer, he was right I didn't need to iterate the needle and the unique results afterwards twice). The solution I updated it with seems to be faster \$\endgroup\$ – Icepickle Jul 30 at 7:30
3
+100
\$\begingroup\$

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

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Nice :) Based on the test on codewars itself, it is also in the same ballpark as my solution :) You could also have ended the if with || !count[c]-- but that may then be less readable :) \$\endgroup\$ – Icepickle Jul 30 at 9:41
  • 1
    \$\begingroup\$ You have presented an alternative solution. Please explain your reasoning (why it is better than the original) so that the author and other readers can learn from your thought process. You got a good start, but it's missing a bit in the review department. Your last sentence "This loops both the strings only once." could be the start of its own paragraph. \$\endgroup\$ – Mast Jul 30 at 9:51
  • 1
    \$\begingroup\$ @Mast got it, thanks. Since other answers already had explained, I skipped that. This looks like a review of OP's self-answer. I'll update when I get some time. \$\endgroup\$ – adiga Jul 30 at 10:07
  • \$\begingroup\$ Thanks, in the end, I went with Ry's answer but once the question becomes open for a bounty, I will share it between some of the answers that helped me the most \$\endgroup\$ – Icepickle Jul 31 at 7:58
  • \$\begingroup\$ @Icepickle replying to your first comment: actually you can just change the condition to: if (!count[c]--). If the character doesn't exists, it will return NaN. And if count[c]-- returns 0 which means the number was already 0 and it is -1 now. \$\endgroup\$ – adiga Jul 31 at 16:14
2
\$\begingroup\$

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

| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

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));
}
| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ This one wouldn't work, as you are only testing the unique characters, but not if all characters are necessary to form the word, for example, this one would fail: scramble('leksa', 'leeks'), where yours would return true, cause all unique letters of leeks are found in leksa, but there aren't enough e's ;) \$\endgroup\$ – Icepickle Jul 30 at 14:07
  • \$\begingroup\$ I see. I misunderstood the challenge then, because this passes all tests on codewars. \$\endgroup\$ – corvus_192 Jul 31 at 15:20
  • \$\begingroup\$ until your click on attempt it indeed passes all :) \$\endgroup\$ – Icepickle Jul 31 at 16:05
2
\$\begingroup\$

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)

| improve this answer | |
\$\endgroup\$
  • 2
    \$\begingroup\$ Looks good :) The only downside would be that you might split on the same letters several times \$\endgroup\$ – Icepickle Jul 30 at 23:27

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.