Given two strings s and t, return true if t is an anagram of s, and false otherwise.

An anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Example 1:

• Input: s = "anagram", t = "nagaram"
• Output: true

Example 2:

• Input: s = "rat", t = "car"
• Output: false

Constraints:

• 1 ≤ s.length, t.length ≤ 5 × 10⁴
• s and t consist of lowercase English letters

Valid Anagram tests your ability to compare character frequencies efficiently using a hash map or fixed-size counting array.

Pattern: Frequency Counting

When comparing whether two collections contain the same elements (ignoring order), count occurrences of each element and compare the counts.

graph TD
    Start["Input Data"] --> Process["Process Element by Element"]
    Process --> Lookup{"Hash Map / Set Lookup"}
    Lookup -- "Match Found" --> Return["Return Indices / Result"]
    Lookup -- "No Match" --> Store["Store in Map / Set"]
    Store --> Process

function isAnagram(s, t) {
  return s.split('').sort().join('') === t.split('').sort().join('');
}

• Time Complexity: O(n log n)
• Space Complexity: O(n)
• Explanation: Sort both strings and compare.

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

• Time Complexity: O(n)
• Space Complexity: O(1)
• Explanation: Count characters in one pass, decrement in the other.

1. Initialize State: Setup necessary pointers, dynamic programming arrays, or hash maps.
2. Iterate & Evaluate: Process the input according to the boundary conditions.
3. Update & Return: Compute the optimal answer and return early or at termination.

How to explain:

1. Start with sorting-based comparison
2. Point out sorting costs O(n log n)
3. Move to frequency counting with a hash map for O(n)
4. Early exit on length mismatch

1. If the lengths differ, they can’t be anagrams.
2. Count the frequency of each character in both strings.
3. A hash map or a 26-element array works well for lowercase letters.

👉 Solve this problem interactively in the DSA Lab