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, in a case-sensitive search.

Examples of Behaviour

Input 1


Output 1


Explanation The substrings are highlighted in bold below:





Note the search MUST be case sensitive for all searches.

Input 2


Output 2


This must work for standard ASCII only. This is code-golf, so shortest number of characters will get the tick of approval. Also please post a non-golfed version of your code along with the golfed version.

  • 2
    \$\begingroup\$ Important test case: abacacaba aac \$\endgroup\$ Commented May 15, 2015 at 21:24
  • \$\begingroup\$ Will the parent string always be longer than the query string ? \$\endgroup\$
    – Optimizer
    Commented May 15, 2015 at 22:52
  • \$\begingroup\$ Oh very good point! Yes @Optimizer, the parent string will always be longer than the query string. \$\endgroup\$ Commented May 16, 2015 at 0:52
  • \$\begingroup\$ @WallyWest What about the additional test case? Should overlapping occurrences of a single permutation be counted? \$\endgroup\$ Commented May 16, 2015 at 3:15
  • 1
    \$\begingroup\$ Can you give a test case and its correct solution for your most recent comment? \$\endgroup\$
    – isaacg
    Commented May 16, 2015 at 8:58

7 Answers 7


Pyth, 11 10 bytes


1 byte golf thanks to @Jakube.


Takes the query string, followed by the parent string on a new line.


z = input()
len(filter(lambda T: sorted(z) == sorted(T), substrings(input())
  • \$\begingroup\$ 1 byte save, simply remove the last character of your solution ;-) \$\endgroup\$
    – Jakube
    Commented May 15, 2015 at 23:19
  • \$\begingroup\$ @Jakube Oh, of course, that's wonderful. \$\endgroup\$
    – isaacg
    Commented May 16, 2015 at 3:02

CJam, 13 bytes


(12 bytes, if overlapping is allowed)


Input goes like:



<query string>
<parent string>

Thanks to Dennis for saving 3 bytes in the overlapping scenario

Try it online here

  • 1
    \$\begingroup\$ You can handle overlapping with the same byte count: ll1$,ew:$\$e= \$\endgroup\$
    – Dennis
    Commented May 16, 2015 at 2:49
  • \$\begingroup\$ @Dennis That's really nice. 12 bytes : l$_,lew:$\e= But not sure if this would be valid now that OP has said that overlapping is not allowed. Let me see if I can reduce my current one. \$\endgroup\$
    – Optimizer
    Commented May 16, 2015 at 8:26

JavaScript ES6, 95 bytes


This is a function that takes two arguments like this: f(parent,query).

It goes through all substrings of the parent string of the length of the query string and sorts them. If they are the same as the sorted query string, it increments n. Sorting string is annoying because it must be converted to an array, sorted, and converted back to a string. Ungolfed and testable code below.

var f = function(p, q) {
  var n = 0
  var s = function(a) {
    return a.split('').sort().join('')
  p.split('').map(function(_, i) {
    n += s(p.substr(i, q.length)) == s(q)
  return n

// testing code below
document.getElementById('go').onclick = function() {
  var parent = document.getElementById('parent').value,
    query = document.getElementById('query').value;
  document.getElementById('output').innerHTML = f(parent, query);
<label>Parent: <input id="parent" value="AdnBndAndBdaBn"/></label><br />
<label>Query:  <input id="query" value="dAn"/></label><br />
<button id="go">Go</button><br />
<samp id="output">&mdash;</samp> anagrams found


Haskell, 77 68 bytes

import Data.List
p#s=sum[1|x<-tails p,sort s==sort(take(length s)x)]


*Main> "AdnBndAndBdaBn" # "dAn"
*Main> "AbrAcadAbRa" # "cAda"
*Main> "abacacaba"# "aac"

How it works: parent string is p, query string is s.

tails creates a list of it's parameter with successively removing the first element, e.g. tails "abcd" -> ["abcd","bcd","cd","d",""]. For every element x of this list take a 1 if the sorted first n elements (where n is the length of s) equal the sorted s. Sum the 1s.

Edit: tails instead of explicit recursion


Python, 61 bytes

f=lambda a,b:a>''and(s(b)==s(a[:len(b)]))+f(a[1:],b)

This is a recursive algorithm. It checks whether the initial characters of the parent string, once sorted, are the same as the query string, sorted. Then, it recursive on the parent string with its first character removed. It terminates when the parent string is empty.


Python 2, 76 70 bytes

This lambda function iteratively compares each sorted substring with the target substring. The matches are counted and returned.

lambda a,d:sum(sorted(d[n:n+len(a)])==sorted(a)for n in range(len(d)))

The ungolfed code:

f = lambda substr, text: sum(
    sorted(text[n:n+len(substr)]) == sorted(substr)
    for n in range(len(text))

def test(tests):
    for t in tests.split():
        substr, text  = t.split(',')
        print t, f(substr, text)

tests = '''ba,abcba dAn,AdnBndAndBdaBn aac,abacacaba'''

and the test output:

ba,abcba 2
dAn,AdnBndAndBdaBn 4
aac,abacacaba 2
  • \$\begingroup\$ ZOUNDS! I never saw that. I will edit and save some bytes. Thanks Jakube. \$\endgroup\$ Commented May 16, 2015 at 10:32

Python 2, 124 118 bytes

Try it here

This is an anonymous lambda function. It can probably still be golfed further.

import re,itertools as i
lambda p,q:sum(len(re.findall('(?='+''.join(i)+')',p))for i in set(i.permutations(q,len(q))))


from itertools import*
import re
def f(p,q):
    for i in set(permutations(q,len(q))):
    print c
  • \$\begingroup\$ don't need re, you can just do string.count(substring) for each permutation \$\endgroup\$ Commented May 15, 2015 at 22:35
  • 2
    \$\begingroup\$ @sirpercival No, string.cound doesn't count overlapping occurrences, like in the f('aaa','aa'). \$\endgroup\$
    – Jakube
    Commented May 15, 2015 at 23:13
  • \$\begingroup\$ ah, good call! i forgot about that. \$\endgroup\$ Commented May 15, 2015 at 23:20
  • 1
    \$\begingroup\$ import re,itertools as i saves 6 chars. (I haven't known before that it works.) \$\endgroup\$
    – randomra
    Commented May 15, 2015 at 23:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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