Leetcode 242 Valid Anagram

In this exercise, we are given 2 strings, and we should return true if and only if they are anagrams.

a. Letters frequencies

A common pattern for this type of exercises is to store the letter frequencies in an array. I usually use new int[256], so that I can do arr[c]++ for a character c instead of arr[c-’a’]++. We can simply reduce the 2 strings to 2 arrays with the frequencies for each letter.

Conversion to letter frequencies

int[] a = new int[256];
int[] b = new int[256];
int n = s.length();
if (t.length() != n) {
    return false;
}
for (int i =0;i<n;i++) {
    a[s.charAt(i)]++;
    b[t.charAt(i)]++;
}

b. Algorithm

First we build the arrays of frequencies, and then simply compare them. If all the values in the 2 arrays are the same we return true, otherwise we return false.

public boolean isAnagram(String s, String t) {
    int[] a = new int[256];
    int[] b = new int[256];
    int n = s.length();
    if (t.length() != n) {
        return false;
    }
    for (int i =0;i<n;i++) {
        a[s.charAt(i)]++;
        b[t.charAt(i)]++;
    }
    for (char c = 'a'; c <='z'; c++) {
        if (a[c] != b[c]) {
            return false;
        }
    }
    return true;
}

c. Time and Space complexities

The tme complexity is O(n) where n is the length of each string. The space complexity is consisting in 2 arrays to store the letter frequencies, but these arrays are of constant size, so the space complexity is O(1).