[Challenge] Anagram Challenge

It’s a new year, and we’re kicking off monthly community code challenges. :tada:

Let’s test your knowledge and your creativity with a challenge initially posted by @oduffy a while back.

Rules to enter:

  • Choose any general-purpose programming language taught on Codecademy, such as Python, JavaScript, Java, or C++.
  • Make sure your code is original and readable; make it your own, but use style conventions and comments to keep things legible.
  • Submit your code (formatted correctly for a forum post) and a picture/GIF of your output by Friday, February 18th at 11:59 PM EST. :clock1:

Beginner Level

Write a function in your favorite programming language that will accept any two strings as parameters and return “1” if they are anagrams and “0” if they are not.

Keep it simple! Focus only on strings composed from uppercase letters (in hex ASCII - from 41 (A) to 5A (Z)) and space characters.

Scroll down and reply to this thread with your code to participate! Don’t just submit your code, remember to explain your solution, too! Submit.


Intermediate Level

Make sure that your answer has no more than O(n + m) time complexity 66, where n is the length of the first string and m of the second.

Efficiency is the name of the game, so shoot for the most direct approach that does not involve len(n)! permutations.

Resources

  • Learn more about Big O notation and time complexity here and here.

Once you’re done…

Share your submission in a post below. Share a picture/GIF of your finished project and include a link to your Codecademy Workspace link so we can see your code.

If you miss the challenge deadline, submit anyway! This is a great opportunity to test your skills and prepare for interviews. Your submissions will help others learn, too.


Happy coding and best of luck! :raised_hands:

1 Like

I’m confused as to what “two strings 43” and " anagrams 387 and 0" mean here? :thinking:

1 Like

Alas, just two typos that got away from me. Good catch!

Edited them out, and now it should make a lot more sense.

1 Like

Ruby 2.7+

def anagram(first, second)
        return first.each_char.tally == second.each_char.tally
end
2 Likes

Java 9+

This function accounts for capitalization and spaces in input string.

I believe the big O runtime is O(n + m). The code iterates over each String’s characters once to convert the Strings to Character arrays, and then over the arrays to add to the maps. Collections::frequency would iterate over the characters again internally, but it would max out at 26 iterations if the word contained every letter and spaces. So the extra iterations would be 27n + 27m in the worst case. Dropping the coefficients yields n + m. There are likely other hidden iterations buried in the internal functions, but they would just add higher coefficients to n + m, which would still be dropped in the end.

public int isAnagram(String subject, String testWord) {

        // Convert each word to Character arrays. Using Collections::frequency requires this as a step
        Character[] subjectArr = subject.toUpperCase().chars().mapToObj(c -> (char) c).toArray(Character[]::new);
        Character[] testWordArr = testWord.toUpperCase().chars().mapToObj(c -> (char) c).toArray(Character[]::new);

        // Store each character and its count in a map
        Map<Character, Integer> subjectMap = new HashMap<>();
        Map<Character, Integer> testWordMap = new HashMap<>();


        // Fill map for starting word
        for (Character c : subjectArr) {
            subjectMap.putIfAbsent(c, Collections.frequency(List.of(subjectArr), c));
        }

        // Fill map for test word
        for (Character c : testWordArr) {
            testWordMap.putIfAbsent(c, Collections.frequency(List.of(testWordArr), c));
        }

        // Remove spaces from maps
        subjectMap.remove(' ');
        testWordMap.remove(' ');

        // If maps are equal, then both words can be made, ergo they are anagrams
        if (subjectMap.equals(testWordMap)) {
            return 1;
        }
        return 0;
    }

https://www.codecademy.com/workspaces/61ef47338f5e57a8e88cdeaf

1 Like

Thanks for another challenge!!

I did mine in C, and it should be able to detect the entire ASCII range of chars, 0 - 127.
It doesn’t mind capitalization so TOD and tod are considered anagrams. I wasn’t sure whether or not space difference should count so I went with yes, meaning:

hello there
hello    there

are not anagrams


main.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <limits.h>
#include "input.h"


char anagram(char* s1, char* s2) {
  // if string lengths don't match it ain't an anagram
  if (strlen(s1) != strlen(s2)) return 0;
  
  // create an array to store the number of each character
  int* count;
  if ((count = (int*)malloc(sizeof(int) * CHAR_MAX)) == NULL) {
    fprintf(stderr, "Failed to allocate %lu bytes at %p!\n", sizeof(int) * CHAR_MAX, count);
  }

  // loop through the strings
  for (int i = 0; i < strlen(s1); i++) {
    // every char in s1 increments that value in count
    count[toupper(s1[i])]++;
    // every char in s2 decrements that value in count
    count[toupper(s2[i])]--;
  }

  // loop through count
  for (int i = 0; i < CHAR_MAX; i++) {
    // if any value is not 0 there was an uneven number of that character and it's not an anagram.
    if (count[i]) {
      free(count);
      return 0;
    }
  }
  
  free(count);
  return 1;
}


int main(void) {
  // get user input
  char* a = input("Enter a first string: ");
  char* b = input("Enter a second string: ");
  
  // find if they are anagrams
  char r = anagram(a, b);
  printf("Result: %s, and %s are %sanagrams!", a, b, r?"":"not ");
  return 0;
}

input.h

char* input(char* msg);

input.c

#include <stdio.h>
#include <stdlib.h>

// custom input function to get variable len string
char* input(char* msg) {
  unsigned int sze = 2;
  char* r;
  if ((r = malloc(sizeof(char) * sze)) == NULL) {
    fprintf(stderr, "Failed to allocate %lu bytes at %p", sizeof(char) * sze, r);
    exit(EXIT_FAILURE);
  }
  printf("%s", msg);
  char c;
  while ((c = getchar()) != '\n') {
    r[sze-2] = c;
    if (realloc(r, ++sze) == NULL) {
      fprintf(stderr, "Failed to allocate %lu bytes at %p", sizeof(char) * sze, r);
      exit(EXIT_FAILURE);
    }
  }
  r[sze-1] = '\0';
  return r;
}

The anagram finder works by creating an array of ints that is CHAR_MAX long or 127 in standard C.
Then looping through s1 and s2 at the same time and incrementing the count for s1 and decrementing the count for s2. At the end if it’s an anagram the entire array will be filled with zeros.

This give a Big O notation of O(n) were n is the length of s1

I was inspired by a geeksforgeeks article for a C# anagram checker I read, but sadly don’t remember were the article is now…
As a summary though they talked about incrementing AND decrementing as opposed to creating two arrays to hold the total number of characters.


Code can be run here: https://replit.com/@ShaylinTRK/CC-Anagram-Finder

Screenshot 2022-01-25 6.26.50 PM
Screenshot 2022-01-25 6.28.41 PM

1 Like

Just some silliness…

>>> def is_anagram(a, b):
	m = sum([(ord(x) % 32) ** 2 for x in a if x.isalpha()])
	n = sum([(ord(x) % 32) ** 2 for x in b if x.isalpha()])
	return m == n

>>> is_anagram("ABC DAB CD", "DC BAD CBA")
True
>>> is_anagram("abcdabcd", "D CB ADC BA")
True
>>> is_anagram("abbeabcd", "DCBADCBA")
False
>>> 

This follows the premise that equal pair sums do not exist once the values are squared and summed.


Even better…

>>> def is_anagram(a, b):
    def f(u):
        return sum([pow(ord(x) % 32, 2) for x in u if x.isalpha()])
    return f(a) == f(b)

>>> is_anagram("School master", "The classroom")
True
>>> 
2 Likes

Love the idea, but I fear your premise may be flawed.
For instance, it’ll pass “CD” as an anagram of “E” ( 9 + 16 = 25 )
or as “A” is 1, you could just pad the strings with them until they match.

3 Likes

So, I’ve had two pops at this.
The first try sorts both strings and then compares them. Fairly short, but felt a little cheap using inbuilt functions to do the heavy lifting.
The second uses a dictionary. Goes through the first string and adds in letters as it goes, then goes through the second taking them out again. If it hits something not in the dictionary or it’s not empty at the end then we know it’s not an anagram.
https://www.codecademy.com/workspaces/61f12135e8251449419d64f6

2 Likes

My JavaScript O(n+m) solution

There are 27 accepted characters. In order to accept the following example as a valid anagram, I ignore spaces.

VACATION TIME
I AM NOT ACTIVE

The other 26 valid capital letters are converted to integers from 1 to 26. The idea was to then let ‘A’ equal 1 and ‘Z’ equal 10000000000000000000000000 and calculate the sum for the 1st string and subtract the sum of the 2nd string. If the result is 0, it is an anagram. But since an integer with 26 digits doesn’t work, I split the number in 2 halfs and store it in an array:

Array[0]:
from A = 1
to M = 1000000000000
Array[1]:
from N = 1
to Z = 1000000000000

This is what the steps look like for the anagram

STATE
TASTE

If the sum of both array items is 0 after summing up the 1string and subtracting the 2nd, it is an anagram.

All conversions are done seperately within the loop in order to save runtime. I hope this comes with low costs.

Workspace with comments:
https://www.codecademy.com/workspaces/61ef3140e8251449419a7e4c

Plain Code

const anagramTester = (str1, str2) => {

  let invalidCharacter = false;
  let validator = [0, 0];

  const calcSum = (str, action) => {
    for (let i = 0; i < str.length; i++){
      let dec = str[i].charCodeAt();
      if(dec===32) continue
      dec = dec - 64;
      if (dec < 1 || dec > 26) {
        invalidCharacter = true;
      } else {
        let n = dec / 13.1 > 1 ? 1 : 0;
        let val = 10 ** (dec % 14 -(1-n));
        action==='add' ? validator[n] += val : validator[n] -= val;
      }
    }
  }
  calcSum(str1, 'add');
  calcSum(str2);

  if (invalidCharacter) return 'Invalid character(s) found: Please enter capital letters from A-Z or spaces only.';

  return (validator[0] === 0 && validator[1] === 0) ? 1 : 0;
}
2 Likes

Yeah, it was too good to be true. Back to the drawing board.

How about,

>>> def is_anagram(a, b):
    def f(u):
        return sum([pow(ord(x), 2) for x in u.upper() if x.isalpha()])
    return f(a) == f(b)

>>> is_anagram("School master", "The classroom")
True
>>> is_anagram('cd', 'e')
False
>>> 

?

Or what about cubing, rather than squaring?

>>> def is_anagram(a, b):
    def f(u):
        return sum([pow(ord(x), 3) for x in u.upper() if x.isalpha()])
    return f(a) == f(b)

>>> is_anagram("School master", "The classroom")
True
>>> is_anagram('cd', 'e')
False
>>> is_anagram("abbeabcd", "DCBADCBA")
False
>>> is_anagram("ABC DAB CD", "DC BAD CBA")
True
>>> is_anagram("abcdabcd", "D CB ADC BA")
True
>>> 

I tried something like that yesterday in JavaScript. For that purpose I had also written a function to test a few character combinations. With the power of 2 of the decimals (I subtracted 64, so I had numbers from 1-26), I had a lot of false pairings. So I tried ** 3, still a lot. Then with ** 4, I posted it. But since the length of the input string isn’t limited, there is an indefinite amount of pairings, so there will always be a false twin, I guess. So I refactored my solution to the upper one, and even this is limited to a maximum of 9 occurrences per character.

2 Likes

It was worth a try. Guess we can scrap that idea. Here is another bit of silliness, though more practical…

>>> def is_anagram(a, b):
	def f(u):
		return sorted([x for x in u.upper() if x.isalpha()])
	return f(a) == f(b)

>>> is_anagram("School master", "The classroom")
True
>>> 
1 Like

So in Python (is it?), you can sort strings? Nice. In JS that wouldn’t have been possible with O(n+m), I guess. And not with different amount of spaces.

const f = (str1, str2) => {
  str1 = str1.split('').sort().join('');
  str2 = str2.split('').sort().join('');
  return str1 === str2
}
1 Like

It may work for smaller strings, but at some point you’re going to get two different strings which can resolve to the same value.
E.g taken to extreme;
a string of 66^3 A’s would be equivalent to 65^3 B’s.
(both would be = 66 * 66 * 66 * 65 * 65 * 65)

I’m not sure if it would be possible to generate a number which would definitely avoid collisions, but it’s certainly got me thinking…
Anyway, please continue with the silliness, it helps keep the grey matter ticking over.

2 Likes

Not strings, lists. The above is a list comprehension. Strings are immutable objects in Python. To put the lists back into string form,

"".join(sorted([x for x in u.upper() if x.isalpha()]))

In terms of Big-O, there are two loops, but they are not nested. sorted() is O(n log n), if I’m not mistaken.

1 Like
str1.split(/\W/g).sort().join('')

That should sort out the spaces and other non-word characters concern. Would still need to apply .toLowerCase() or .toUpperCase() to resolve case differences: a !== A.

str1.toUpperCase().split(/\W/g).sort().join('')
1 Like

More Python silliness of a destructive nature…

>>> def is_anagram (a, b):
    def f(u):
        return [x for x in u.upper() if x.isalpha()]
    p = f(a)
    q = f(b)
    if len(p) == len(q):
        for x in p[:]: p.remove(x); q.remove(x)
    return len(p) == len(q) == 0

>>> is_anagram("School master", "The classroom")
True
>>> is_anagram("cd", "e")
False
>>> 

Porting to JavaScript

 > is_anagram = function (a, b) {
       function f(u) {
           return u.toUpperCase().split(/\W/g).join('')
       }
       p = f(a)
       q = f(b)
       if (p.length === q.length) {
           for (let x of p.slice()) {
               p = p.replace(x, '')
               q = q.replace(x, '')
           }
       }
       return p.length === q.length && p.length === 0
   }
<- ...
 > is_anagram("no alibi err badly", "near by libra idol")
<- true

Done in the console so let and const are not used. Same rules do not apply in code.


Difference being in the Python version we work with lists; in the JS version we work with strings.


Credit to Colin Dexter, et al (Morse) for the anagram.

Edit: fix code errors

Javascript O(n)

Here is another variation of the popular approach to temporarily store the letters in an object. It doesn’t matter how many spaces are includes, so this is an anagram:

‘dormitory’, ‘dirty room’

Only one iteration is needed.

Step 1

Find the length of the longer string. That length is taken for the loop.

Step 2

Pad the shorter string with white spaces so shorterString[len-1] isn’t undefined.

Step 3

Start the loop and break it if there is an invalid character using a regular Expression.

Step 4

string1[i] and string2[i] are done with the same loop.

  • If there is a key string1[i] / string2[i] in the object, delete it and count down by 1 for each.
  • If there is no string1[i] / string2[i] in the object, add it and count up by 1 for each.
  • If string1[i] and string2[i] are equal, don’t do anything.

Step 5

  • Return 1 if counter is 0 (is anagram)
  • Return 0 if counter > 0 (is not anagram)
  • Return string if counter < 0 (invalid input)
const a = 'dormitory'
const b = 'dirty room'

const findAnagram = (a, b) => {
  const len = Math.max(a.length, b.length);
  
  //handle edge case: strings have diffent lengths
  a = a.padEnd(len, ' ');
  b = b.padEnd(len, ' ');

  const regEx = /[a-zA-Z]|(\s)/;
  const obj = {};
  let count = 0;

  for(i=0; i<len; i++){

      let charA = a[i].toUpperCase();
      let charB = b[i].toUpperCase();

      //test for valid input
      if(!regEx.test(charA) || !regEx.test(charB)) {
        count = -1
        break
      }

      if(charA !== 0 && obj[charA]) {
        delete obj[charA]
        count--
      } 
      else if(charA !== 0 && !obj[charA]) {
        obj[charA] = charA;
        count++
      } 
      if(charB !== 0 && obj[charB]) {
        delete obj[charB]
        count--
      } 
      else if(charB !== 0 && !obj[charB]) {
        obj[charB] = charB;
        count++
      } 
  }
  if(count < 0) return 'Please enter a string of letters from a-z/A-Z and spaces only.';
  return count===0 ? 1 : 0
}
console.log(findAnagram(a, b))

Workspace