# Anagram counter

Homework prompt was:

You are given two strings, a ‘parent’ string and a ‘query’ string respectively. Your task is to determine how many times the query string – or an anagram of the query string appears in the parent string.

NOTE: There are a range of solutions to this problem. With a little thought, you can massively improve the efficiency of your solution. The optimal solution runs almost instantly even for extremely large (1 million+ characters) parent and query strings.

### Sample Input

AdnBndAndBdaBn
dAn


### Sample Output

4


### Explanation

The substrings are highlighted below.

• AdnBndAndBdaBn
• AdnBndAndBdaBn
• AdnBndAndBdaBn
• AdnBndAndBdaBn

It had to take input from keyboard and print to stdout. My solution was to "slide" a window picking up N, where N == query string length and counting char frequency to determine if that bit is an anagram. I did it in Scala, but I feel it could be improved. Any pointers?

My code:

object AnagramDetection {

def main(args: Array[String]) {
println(anagramCount(input, query))
}

def anagramCount(input: String, query: String): Int = {
var count = 0
if(query.length < input.length) {

val keyMap = (str: String) =>  str.groupBy(identity).mapValues(_.length)
val keyCount = keyMap(query)
for(start <- 0 until input.length - query.length) {
if(keyMap(input.substring(start, start + query.length)) == keyCount) {
count += 1
}
}

}
count
}

}


The for loop should be replaced by input.sliding(query.length).
The if (…) { count += 1 } statement should be replaced by count(predicate).
If performance is a concern, you should be able to avoid re-evaluating keyMap from scratch for each window, by using the previous keyMap and decrementing and incrementing the counts of the characters at the margins.