2
\$\begingroup\$

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
  }

}
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.