Find Permutations of String in Scala

Question

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 =         
    large.sliding(small.length).filter(_.diff(small).isEmpty).length

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

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

Archived (faulty)

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

Please evaluate it for correctness and speed.

Answer 1

• 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.