Given a smaller strings and a bigger string b, design an algorithm to find all permuta­tions of the shorter string within the longer one.

def findPermutations(large: String, small: String): Int =         

@ findPermutations("cbabadcbbabbcbabaabccbabc", "abbc") 
res11: Int = 7

@ findPermutations("xaabx", "abb") 
res12: Int = 0

Archived (faulty)

@ def findPermutations(large: String, small: String): Int = 
       .filter(_.toSet == small.toSet)
defined function findPermutations

Please evaluate it for correctness and speed.

  • 1
    \$\begingroup\$ Algorithm is faulty: findPermutations("xaabx", "abb") and the .toList doesn't serve any useful purpose. \$\endgroup\$
    – jwvh
    Feb 17 '21 at 9:13
  • \$\begingroup\$ Thanks, @jwvh. Please check out my update! \$\endgroup\$ Feb 19 '21 at 2:17
  • correct - As far as I can tell, yes.
  • concise - A filter() followed by a .length (or .size) can be simplified: large.sliding(small.length).count(_.diff(small).isEmpty)
  • fast - Could be faster, but it wouldn't be as concise.

Consider the following: findPermutations("abcxcba", "cab")

Under the current design that would be 5 invocations of _.diff(small).isEmpty, but 3 of the 5 are rather pointless. No test string containing a character not found in the target string is worth the effort.

It'd be nice if the sliding window could "jump" over non-target characters. Doable, but not trivial.


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.