Anagram counter

Question

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]) {
    val input = io.StdIn.readLine()
    val query = io.StdIn.readLine()
    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
  }

}

Answer 1

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.