Arrays are essentially simple hash tables, but the size of an array is not limitless.

242. Valid Anagram

LeetCode Problem Link (opens new window)

Given two strings s and t, write a function to determine if t is an anagram of s.

Example 1: Input: s = "anagram", t = "nagaram" Output: true

Example 2: Input: s = "rat", t = "car" Output: false

Note: You may assume the strings contain only lowercase alphabets.

Thought Process

Let's start with a brute force solution: using two for loops while keeping track of character repetitions. Clearly, this approach has a time complexity of O(n^2).

We won't delve into the brute force solution here and will directly explore a more efficient method.

An array is essentially a simple hash table, and since the problem statement specifies that the strings contain only lowercase letters, we can define an array to record the frequency of each character in string s.

If you need to understand the theoretical basics about arrays, sets, and maps, you can check this article: Hash Table Basics (opens new window)

How large should the array be? Defining an array called record with a size of 26 is sufficient, initialized to 0, because the ASCII values for characters 'a' to 'z' are 26 consecutive integers.

For example, consider strings s= "aee" and t = "eae".

Here's the animation of the operation:

Define an array called record that will record the frequency of each character in string s.

To map a character to an array (or hash table) index, since the ASCII values for characters 'a' to 'z' are 26 consecutive integers, character 'a' maps to index 0, and character 'z' maps to index 25.

When iterating through string s, simply increase the count of the element at index s[i] - ‘a’ by 1. You don't need to memorize the ASCII values for character a; simply getting a relative value is enough. This allows us to count the occurrences of characters in string s.

To verify whether string t has the same characters, similarly, when traversing string t, decrement the count of the corresponding character in the hash table by 1.

Finally, check if any elements in the record array are non-zero. If any are, it indicates that either string s or t has extra or missing characters—return false.

In the end, if all elements in the record array are zero, it means the two strings are anagrams of each other—return true.

The time complexity is O(n), and, since we have defined an auxiliary array of constant size, the space complexity is O(1).

C++ code is as follows:

class Solution {
public:
    bool isAnagram(string s, string t) {
        int record[26] = {0};
        for (int i = 0; i < s.size(); i++) {
            // No need to remember the ASCII value of ‘a’. A relative value is enough.
            record[s[i] - 'a']++;
        }
        for (int i = 0; i < t.size(); i++) {
            record[t[i] - 'a']--;
        }
        for (int i = 0; i < 26; i++) {
            if (record[i] != 0) {
                // If any element in `record` is not zero, it means either string `s` or `t` has extra or missing characters.
                return false;
            }
        }
        // If all elements in `record` are zero, the two strings are anagrams.
        return true;
    }
};

• Time Complexity: O(n)
• Space Complexity: O(1)

Versions in Other Languages

Java:

/**
 * 242. Valid Anagram Dictionary Approach
 * Time Complexity O(m+n), Space Complexity O(1)
 */
class Solution {
    public boolean isAnagram(String s, String t) {
        int[] record = new int[26];

        for (int i = 0; i < s.length(); i++) {
            record[s.charAt(i) - 'a']++;     // No need to remember the ASCII of ‘a’. A relative value suffices.
        }

        for (int i = 0; i < t.length(); i++) {
            record[t.charAt(i) - 'a']--;
        }
        
        for (int count: record) {
            if (count != 0) {               // If any element in the `record` array is non-zero, it means either string `s` or `t` has extra or fewer characters.
                return false;
            }
        }
        return true;                        // If all elements in the `record` array are zero, the two strings are anagrams.
    }
}

Python:

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        record = [0] * 26
        for i in s:
            # No need to remember the ASCII value of 'a’. Just find a relative value.
            record[ord(i) - ord("a")] += 1
        for i in t:
            record[ord(i) - ord("a")] -= 1
        for i in range(26):
            if record[i] != 0:
                # If any elements in `record` are non-zero, it means either string `s` or `t` has extra or missing characters.
                return False
        return True

Python Version 2 (demonstrating an approach using defaultdict instead of an array as a hash table):

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        from collections import defaultdict
        
        s_dict = defaultdict(int)
        t_dict = defaultdict(int)
        for x in s:
            s_dict[x] += 1
        
        for x in t:
            t_dict[x] += 1
        return s_dict == t_dict

Python Version 3 (demonstrating a more convenient solution using Counter):

class Solution(object):
    def isAnagram(self, s: str, t: str) -> bool:
        from collections import Counter
        a_count = Counter(s)
        b_count = Counter(t)
        return a_count == b_count

Go:

func isAnagram(s string, t string) bool {
    record := [26]int{}
    
    for _, r := range s {
        record[r-rune('a')]++
    }
    for _, r := range t {
        record[r-rune('a')]--
    }

    return record == [26]int{}   // If any element in the `record` array is non-zero, it means either string `s` or `t` has extra or missing characters.
}

Go Version 2 (only iterates through strings once):

func isAnagram(s string, t string) bool {
	if len(s) != len(t) {
		return false
	}
	records := [26]int{}
	for index := 0; index < len(s); index++ {
		if s[index] == t[index] {
			continue
		}
		sCharIndex := s[index] - 'a'
		records[sCharIndex]++
		tCharIndex := t[index] - 'a'
		records[tCharIndex]--
	}
	for _, record := range records {
		if record != 0 {
			return false
		}
	}
	return true
}

JavaScript:

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var isAnagram = function(s, t) {
    if(s.length !== t.length) return false;
    const resSet = new Array(26).fill(0);
    const base = "a".charCodeAt();
    for(const i of s) {
        resSet[i.charCodeAt() - base]++;
    }
    for(const i of t) {
        if(!resSet[i.charCodeAt() - base]) return false;
        resSet[i.charCodeAt() - base]--;
    }
    return true;
};

var isAnagram = function(s, t) {
  if(s.length !== t.length) return false;
  let char_count = new Map();
  for(let item of s) {
    char_count.set(item, (char_count.get(item) || 0) + 1) ;
  }
  for(let item of t) {
    if(!char_count.get(item)) return false;
    char_count.set(item, char_count.get(item)-1);
  }
  return true;
};

TypeScript:

function isAnagram(s: string, t: string): boolean {
    if (s.length !== t.length) return false;
    let helperArr: number[] = new Array(26).fill(0);
    let pivot: number = 'a'.charCodeAt(0);
    for (let i = 0, length = s.length; i < length; i++) {
        helperArr[s.charCodeAt(i) - pivot]++;
        helperArr[t.charCodeAt(i) - pivot]--;
    }
    return helperArr.every(i => i === 0);
};

Swift:

func isAnagram(_ s: String, _ t: String) -> Bool {
    if s.count != t.count {
        return false
    }
    var record = Array(repeating: 0, count: 26)
    let aUnicodeScalar = "a".unicodeScalars.first!.value
    for c in s.unicodeScalars {
        record[Int(c.value - aUnicodeScalar)] += 1
    }
    for c in t.unicodeScalars {
        record[Int(c.value - aUnicodeScalar)] -= 1
    }
    for value in record {
        if value != 0 {
            return false
        }
    }
    return true
}

PHP:

class Solution {
    /**
     * @param String $s
     * @param String $t
     * @return Boolean
     */
    function isAnagram($s, $t) {
        if (strlen($s) != strlen($t)) {
            return false;
        }
        $table = [];
        for ($i = 0; $i < strlen($s); $i++) {
            if (!isset($table[$s[$i]])) {
                $table[$s[$i]] = 1;
            } else {
                $table[$s[$i]]++;
            }
            if (!isset($table[$t[$i]])) {
                $table[$t[$i]] = -1;
            } else {
                $table[$t[$i]]--;
            }
        }
        foreach ($table as $record) {
            if ($record != 0) {
                return false;
            }
        }
        return true;
    }
}

Rust:

impl Solution {
    pub fn is_anagram(s: String, t: String) -> bool {      
        let mut record = vec![0; 26];
        
        let baseChar = 'a';
        
        for byte in s.bytes() {
            record[byte as usize - baseChar as usize] += 1;
        } 
        for byte in t.bytes() {
            record[byte as usize - baseChar as usize] -= 1;
        } 

        record.iter().filter(|x| **x != 0).count() == 0
    }
}

Scala:

object Solution {
  def isAnagram(s: String, t: String): Boolean = {
    // If the lengths of the two strings are not equal, return false immediately.
    if (s.length != t.length) return false
    val record = new Array[Int](26) // Record the occurrence of each letter
    // Traverse the string; for string `s`, increment the corresponding record for each character, and for string `t`, decrement it.
    for (i <- 0 until s.length) {
      record(s(i) - 97) += 1
      record(t(i) - 97) -= 1
    }
    // If not equal, return false immediately.
    for (i <- 0 until 26) {
      if (record(i) != 0) {
        return false
      }
    }
    // If no false return earlier, it means a successful match, return true. The return can be omitted.
    true
  }
}

C#:

 public bool IsAnagram(string s, string t) {
         int sl=s.Length, tl=t.Length;
        if(sl!=tl) return false;
        int[] a = new int[26];
        for(int i = 0; i < sl; i++){
             a[s[i] - 'a']++;
             a[t[i] - 'a']--;
        }       
        foreach (int i in a)
        {
            if (i != 0)
                return false;
        }
        return true;
    }

C

bool isAnagram(char* s, char* t) {
    int len1 = strlen(s), len2 = strlen(t);
    if (len1 != len2) {
        return false;
    }

    int map1[26] = {0}, map2[26] = {0};
    for (int i = 0; i < len1; i++) {
        map1[s[i] - 'a'] += 1;
        map2[t[i] - 'a'] += 1;
    }
    
    for (int i = 0; i < 26; i++) {
        if (map1[i] != map2[i]) {
            return false;
        }
    }
    
    return true;
}

Related Problems

• 383. Ransom Note (opens new window)
• 49. Group Anagrams (opens new window)
• 438. Find All Anagrams in a String (opens new window)