Anagrams Within Words

February 21, 2014

Our algorithm slides a window the length of the search string along the target string, at each step comparing a frequency count of the letters in the window with a frequency count of the letters in the search string. As the window slides along the target string, the frequency count is updated by removing the farthest-back letter from the current count and adding the new letter to the count:

(define (anagram-in-word needle haystack)
  (let* ((len (string-length needle))
         (stop (string-length haystack))
         (needle (sort charlist needle)))
         (window (sort charlist haystack)))))
    (let loop ((lo 0) (hi (- len 1)) (window window))
      (cond ((= hi stop) #f)
            ((equal? needle window) #t)
            (else (loop (+ lo 1) (+ hi 1)
                        (insert (string-ref haystack hi)
                          (remove (string-ref haystack lo)

The frequency count is stored as a list of characters in alphabetical order, without counts; we use Scheme’s equal? predicate to determine if two lists are the same. Here are the two auxiliary functions:

(define (remove x xs) ; delete first occurrence of x in xs
    (lambda () (split-while (lambda (c) (char<? c x)) xs))
    (lambda (front back) (append front (cdr back)))))

(define (insert x xs) ; insert x in order in xs
    (lambda () (split-while (lambda (c) (char<? c x)) xs))
    (lambda (front back) (append front (list x) back))))

Here are the two examples:

> (anagram-in-word "cat" "actor")
> (anagram-in-word "car" "actor")

We used take and split-while from the Standard Prelude. You can run the program at

About these ads

Pages: 1 2

13 Responses to “Anagrams Within Words”

  1. some posiblidades were missing, the ideal thing would be with a ringlet but I feel sleepy and want to sleep, greetings

    def check_anagr(anagram, string):
    lib = {}
    string = str(string)
    for x in range(3):
    lib[x] = string[x:x+1]
    posibilidades = ['110', '100', '000', '001', '011', '111', '220','200', '222','211', '112', '002','022', '020', '012', '112', '021', '212', '221', '121', '120', '102']
    for i in posibilidades:
    r = i
    var = ‘{}{}{}’.format(lib[int(r[0])], lib[int(r[1])], lib[int(r[2])])
    if anagram == var:
    return True
    return False

    >>> check_anagr(‘cat’, ‘actor’)
    >>> check_anagr(‘car’, ‘actor’)

  2. Paul said

    In Python.

    from collections import Counter
    from itertools import islice, tee, izip
    def update(counter, a, b):
        'replace a by b in Counter'
        counter[b] += 1
        counter[a] -= 1
        if counter[a] == 0:
            del counter[a]
    def anagram(first, second):
        ita, itb = tee(iter(second))
        target = Counter(first)
        actual = Counter(islice(itb, len(first)))
        if target == actual:
            return True
        for a, b in izip(ita, itb):
            update(actual, a, b)
            if target == actual:
                return True
        return False
    print anagram("trel", "appletree") # True
    print anagram("reel", "appletree") # False
    print anagram("diep", "parallellepipedum") # True
    print anagram("dier", "parallellepipedum") # False
  3. /* header files */
    #include // get access to printf() and scanf()
    #include // get access to boolean values
    #include // get access to strlen()

    /* function prototypes */
    bool searchForChar(char c, char* small_word);
    bool isAnagram(char* small_word, char* large_word);

    /* function definitions */
    int main(void)
    char* small_word;
    char* large_word; // set variable for the 2 words

    printf(“Small word is: “); // ask for the small one
    scanf(“%s”, small_word);

    printf(“Large word is: “); // ask for the large one
    scanf(“%s”, large_word);

    char* result;

    if (isAnagram(small_word, large_word)) result = “match!”; // check and print the result
    else result = “no matching!”;

    printf(“%s\n”, result);

    /* for example, we have “cat” and “actor”.
    we are going to divide “actor” into triplets like that (act, cto, tor)
    then we will test matching between each triplet and the small word
    if matching present our function will return (true) */

    bool isAnagram(char* small_word, char* large_word)
    int len_of_small = strlen(small_word); // get the length of the small word

    int len_of_large = strlen(large_word); // get the length of the large one

    int counter; // set a counter to check full matching

    for (int i = 0; i <= len_of_large – len_of_small; i++) // iterate over the large word till the index before the end by the length of the small one
    counter = 0; // set the counter at zero

    for (int j = i; j < i + len_of_small; j++) // iterate over the large word from the current index (i) for the length of the small
    if(searchForChar(large_word[j], small_word)) counter++; // check if the current char is present in the small word and if so update counter

    if (counter == len_of_small ) return true; // if counter reach the length of the small word return true

    return false; // else, return false

    bool searchForChar(char c, char* small_word)
    for (int i = 0, len = strlen(small_word); i < len; i++) // iterate over the small word and see if the char sent from prev. function exists in it
    if (small_word[i] == c)
    return true; // if so, return true

    return false; // else, return false

  4. GyrosOfWar said

    Lazy solution in Clojure using math.combinatorics/permutations:

  5. PHP Solution:

    Enter anagram: cat
    Enter word: actor

    Enter anagram: car
    Enter word: actor

    Enter anagram: top
    Enter word: boptin

    Enter anagram: butt
    Enter word: tubtin

  6. Toxic said

    In Java code:

    public static boolean testAnagram(String originalWord, String containedWord)
    char [] first = originalWord.toCharArray();//Get the first word and store it into a character array.
    char [] second = containedWord.toCharArray();//Get the second word and store it into a character array.
    int [] index = new int[second.length];//An int array that stores the index of matching letters contained in the original array.
    int counter = 0;//Keep count of the index storage position.

    //Compare each character of both words.

    for(int i = 0; i < second.length; i++)
    for(int j = 0; j < first.length; j++)
    if(second[i] == first[j])
    index[counter] = j; //Store matching letters.
    counter++; //Increment the index storage position.
    break;//Break for loop.

    if(counter < second.length)return false;//If not all letters were found.

    //get the distance between the indices which should be no more than one
    //less than the contained word length (to qualify as an anagram)

    for(int i = 0; i < index.length; i++)
    for(int j = 0; j = second.length) return false;

    //If all qualifications are met.
    return true;

  7. vibhumishra007 said

    hello Friends
    Solution in c—->

    char arr1[4];
    int flag=0;
    void swap(char*,char*);
    void permut(char*,int ,int);
    void swap(char *x,char *y)
    char temp;
    void permut(char *a,int i,int n)
    int j;
    char *ptr=NULL;

    void main()
    char arr[]="actor";

  8. […] implemented the Anagrams Within Words programming puzzle from Programming Praxis in Python, a language I haven’t used since my […]

  9. matthew said

    A late entry here in C++: use a multiset (possibly with negative element counts) to store the difference between target characters and the characters in the string being searched. Incrementally keep track of the size of the difference and output the string offset if difference is zero.

    #include <stdio.h>
    #include <string.h>
    #include <assert.h>
    template <typename Element, int N>
    class MSet {
      MSet() : elems(), sz(0) {}
      void add(Element c) {
        if (++elems[c] > 0) sz++;
        else sz--;
      void sub(Element c) {
        if (--elems[c] < 0) sz++;
        else sz--;
      int size() const { return sz; }
      int elems[N];
      int sz;
    void check (const char *s, const char *t)
      int slen = strlen(s);
      int tlen = strlen(t);
      assert(slen <= tlen);
      printf("'%s' '%s':",s,t);
      MSet<unsigned char, 256> mset;
      for(int i = 0; i < slen; i++) {
        mset.sub(s[i]); mset.add(t[i]);
      if (mset.size() == 0) printf(" %d", 0);
      for(int i = slen; i < tlen; i++) {
        mset.sub(t[i-slen]); mset.add(t[i]);
        if (mset.size() == 0) printf(" %d", i-slen+1);
    int main()
      check("foo","foo foo");
  10. A not so efficient solution in Python:

    import itertools
    def anagram(a, b):
        for p in itertools.permutations(a, len(a)):
            if b.find(''.join(p)) >= 0:
                return True
        return False
    for w1, w2 in (('cat', 'actor'), ('car', 'actor')):
        print("%s %s -> %s" % (w1, w2, anagram(w1, w2)))
  11. rock321987 said

    Here is O(nk) solution using Sliding window algo..i was asked this question in amazon..i was not able to solve it there more efficient approach??

    #include <cstdio>
    #include <string>
    #include <iostream>
    using namespace std;
    int calc(string arr, string str)
    	if (arr.length() > str.length()) {
    		return -1;
    	int length = arr.length(), freqarr[255] = {0}, freqstr[255] = {0};
    	for (int i = 0;i < length;i++) {
    	for (int i = 0;i <= str.length() - length;i++) {
    		int flag = 0;
    		for (int j = i;j < i + length;j++) {
    			char tmp =;
    			//printf("%c\n", tmp);
    			if (freqarr[tmp] >= freqstr[tmp]) {
    			} else {
    				flag = 1;
    		if (flag == 0) {
    			return i;
    		} else {
    			if (i != str.length() - length) {
    				freqstr[ + length)]++;
    	return -1;
    int main()
    	while (1) {
    		string arr, str;
    		cin >> arr >> str;
    		int x = calc(arr, str);
    		if (x == -1) {
    			printf("Not Found\n");
    		} else {
    	return 0;

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


Get every new post delivered to your Inbox.

Join 616 other followers

%d bloggers like this: