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.

• jwvh: Algorithm is faulty: findPermutations("xaabx", "abb") and the .toList doesn't serve any useful purpose.
• Kevin Meredith: Thanks, @jwvh. Please check out my update!

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.