Anagram Check: flowchart, algorithm and program

This program reads two lowercase words and decides if they are anagrams, meaning they use exactly the same letters the same number of times. It keeps one counter per letter: letters of the first word add one, letters of the second word subtract one, and if every counter ends at zero the words match.

▶ Watch the dry run step by step →

Algorithm

  1. Step 1: Start.
  2. Step 2: Set count[26] = 0, isAnagram = 1.
  3. Step 3: Read s1, s2.
  4. Step 4: If strlen(s1) != strlen(s2), go to step 5; otherwise go to step 6.
  5. Step 5: Set isAnagram = 0. Go to step 15.
  6. Step 6: Set i = 0.
  7. Step 7: If s1[i] != '\0', go to step 8; otherwise go to step 10.
  8. Step 8: count[s1[i]-'a']++; count[s2[i]-'a']--.
  9. Step 9: Increase i by 1. Go to step 7.
  10. Step 10: Set i = 0.
  11. Step 11: If i < 26, go to step 12; otherwise go to step 15.
  12. Step 12: If count[i] != 0, go to step 13; otherwise go to step 14.
  13. Step 13: Set isAnagram = 0; break. Go to step 15.
  14. Step 14: Increase i by 1. Go to step 11.
  15. Step 15: If isAnagram == 1, go to step 16; otherwise go to step 17.
  16. Step 16: Print "The words are anagrams". Go to step 18.
  17. Step 17: Print "The words are not anagrams".
  18. Step 18: Stop.

Program in C, Python and Java

Anagram Check program in C

#include <stdio.h>
#include <string.h>

int main() {
    char s1[100], s2[100];
    int count[26] = {0};
    int i, isAnagram = 1;

    printf("Enter first word: ");
    scanf("%s", s1);
    printf("Enter second word: ");
    scanf("%s", s2);

    if (strlen(s1) != strlen(s2)) {
        isAnagram = 0;
    } else {
        for (i = 0; s1[i] != '\0'; i++) {
            count[s1[i] - 'a']++;
            count[s2[i] - 'a']--;
        }
        for (i = 0; i < 26; i++) {
            if (count[i] != 0) {
                isAnagram = 0;
                break;
            }
        }
    }

    if (isAnagram)
        printf("The words are anagrams\n");
    else
        printf("The words are not anagrams\n");
    return 0;
}

Anagram Check program in Python

s1 = input("Enter first word: ")
s2 = input("Enter second word: ")
count = [0] * 26
is_anagram = True

if len(s1) != len(s2):
    is_anagram = False
else:
    for i in range(len(s1)):
        count[ord(s1[i]) - ord('a')] += 1
        count[ord(s2[i]) - ord('a')] -= 1
    for i in range(26):
        if count[i] != 0:
            is_anagram = False
            break

if is_anagram:
    print("The words are anagrams")
else:
    print("The words are not anagrams")

Anagram Check program in Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int[] count = new int[26];
        boolean isAnagram = true;

        System.out.print("Enter first word: ");
        String s1 = sc.next();
        System.out.print("Enter second word: ");
        String s2 = sc.next();

        if (s1.length() != s2.length()) {
            isAnagram = false;
        } else {
            for (int i = 0; i < s1.length(); i++) {
                count[s1.charAt(i) - 'a']++;
                count[s2.charAt(i) - 'a']--;
            }
            for (int i = 0; i < 26; i++) {
                if (count[i] != 0) {
                    isAnagram = false;
                    break;
                }
            }
        }

        if (isAnagram)
            System.out.println("The words are anagrams");
        else
            System.out.println("The words are not anagrams");
    }
}

Sample input: first = listen, second = silent
Output: Enter first word: Enter second word:

How it works

  • count[26] holds one counter for each letter, with count[0] for 'a' up to count[25] for 'z'. The expression s1[i] - 'a' turns a letter into its index.
  • First the program compares strlen(s1) and strlen(s2). If the lengths differ, isAnagram becomes 0 straight away, since the words can't use the same letters.
  • In the first loop, count[s1[i] - 'a']++ adds one for each letter of s1 and count[s2[i] - 'a']-- removes one for each letter of s2. Matching letters cancel out.
  • The second loop checks all 26 counters. If any count[i] is not 0, a letter appears a different number of times in the two words, so isAnagram is set to 0 and the loop stops with break.
  • For listen and silent, every letter is added once and removed once, so all counters return to 0 and the program prints 'The words are anagrams'.

Dry run (trace table)

StepLineBoxcountisAnagrams1s2iOutput
14Start
27count[26] = 0, isAnagram = 1all 01
312Read s1, s2all 01listensilent
414strlen(s1) != strlen(s2)?1listensilent
517i = 010
617s1[i] != '\0'?0
719count[s1[i]-'a']++; count[s2[i]-'a']--l=+1, s=-10
817i++l=+1, s=-11
917s1[i] != '\0'?1
1019count[s1[i]-'a']++; count[s2[i]-'a']--l=+1, s=-1 (i: +1-1=0)1
1117i++l=+1, s=-12
1217s1[i] != '\0'?2
1319count[s1[i]-'a']++; count[s2[i]-'a']--l=0, s=02
1417i++all 03
1517s1[i] != '\0'?3
1619count[s1[i]-'a']++; count[s2[i]-'a']--t=+1, e=-13
1717i++t=+1, e=-14
1817s1[i] != '\0'?4
1919count[s1[i]-'a']++; count[s2[i]-'a']--t=+1, e=0, n=-14
2017i++t=+1, n=-15

Time and space complexity

Time: O(n) · Space: O(1). Each word is scanned once (n letters) and the count array has a fixed size of 26.

Common mistakes

  • Skipping the length check. Without it, the loop runs over s1's length and can read past the end of a shorter s2, giving wrong results.
  • Forgetting to initialise count with {0}. Garbage values in the array make the final check fail even for real anagrams.
  • Entering uppercase letters or digits. s1[i] - 'a' then gives an index outside 0 to 25 and writes outside the array, so the program expects lowercase input only.

Viva questions

Q1. What is the purpose of the count[26] array, and why is it initialised with {0}?

It holds one counter for each letter a to z. It starts at all zeros so that the net count of each letter is correct, and if the words are anagrams every counter returns to zero.

Q2. Why do we compare strlen(s1) and strlen(s2) first (line 14)?

Words of different lengths can never be anagrams, so we reject them straight away. It also keeps the loop safe, because the loop reads s2[i] using the length of s1 and would otherwise run past the end of a shorter s2.

Q3. What does count[s1[i] - 'a']++ do? Work it out for the letter 'c'.

It converts the letter to an index from 0 to 25 by subtracting 'a'. For 'c' the index is 'c' - 'a' = 2, so count[2] goes up by one.

Q4. Why do we increment for s1 and decrement for s2 in the same loop?

Each letter in s1 adds one and each matching letter in s2 removes one. If both words have the same letters in the same quantities, every counter ends at zero.

Q5. What happens if the user enters uppercase letters, such as 'Listen' and 'Silent'? Does the program work?

No. 'L' - 'a' is a negative number, so the program writes outside the count array, which is undefined behaviour. To fix it, convert both words to lowercase with tolower() before counting.

Q6. What would happen with an edge case where both strings are empty, or with the words 'abc' and 'abd'?

Two empty strings have equal length, the loop does nothing, all counts stay zero, and the program says they are anagrams. For 'abc' and 'abd', count['c'] ends at 1 and count['d'] at -1, so it says not anagrams.

Q7. What is the time and space complexity of this program?

The time is O(n) for a word of length n, plus a fixed 26-step check, so it is linear. The space is O(1) extra, because the count array is always 26 integers.

Q8. What would you change to make the program handle words with spaces, digits or any character?

Make count[256] and index it with (unsigned char)s1[i] instead of subtracting 'a'. You would also read the input with fgets instead of scanf("%s"), since scanf stops at a space.

Frequently asked questions

What is an anagram?

Two words are anagrams if they contain the same letters with the same frequencies, only in a different order, like listen and silent.

Why do we use s1[i] - 'a' as the array index?

Characters are stored as numbers in order, so subtracting 'a' maps 'a' to 0, 'b' to 1 and so on up to 'z' at 25, which fits the 26-element count array.

Why add for one word and subtract for the other instead of using two arrays?

One array is enough: if both words have the same letters, the additions and subtractions cancel to zero. It saves memory and needs only one final check.

More programs

← All programs

Try AI Flowchart free →