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
}
}