1. Understanding the Problem

You are given two strings, s and t. Your task is to write a function that returns True if t is an anagram of s, and False otherwise.

What is an Anagram?

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.

The Rules & Edge Cases:

• Both strings consist of lowercase English letters.
• If the strings have different lengths, they immediately cannot be anagrams.

Quick Examples

• s = "anagram", t = "nagaram" — True. Both have three 'a's, one 'n', one 'g', one 'r', and one 'm'.
• s = "rat", t = "car" — False. They do not share the exact same character frequencies.

2. The Naive Approach: Sorting

If two strings are anagrams, they must contain the exact same characters in the exact same quantities. Therefore, the most intuitive human approach is to simply alphabetize (sort) both strings. If the sorted versions are identical, they are anagrams.

Trade-off Analysis

While sorting is easy to write in code (often just one line), it is computationally heavy when dealing with massive strings.

• Time Complexity: O(N log N) — This is the standard time complexity for the best sorting algorithms. It is decent, but we can do better.
• Space Complexity: O(1) or O(N) — Depending on the programming language, sorting a string might require creating a new character array in memory.

3. The Optimal Approach: The Frequency Array (O(N) Time)

To pass a senior-level technical interview, we want to drop our time complexity down to O(N). We can achieve this by counting the occurrences of each character instead of sorting them.

Because the problem guarantees we are only dealing with lowercase English letters, there are exactly 26 possible characters. We can create a simple array of size 26 to act as our "counter". We iterate through both strings simultaneously: for every character in the first string, we increment its specific count. For every character in the second string, we decrement its count.

If the two strings are perfect anagrams, every single increment will be perfectly offset by a decrement, leaving our counter array completely filled with zeros at the end.

4. The Logic Step-by-Step

1. Length Check: First, check if s and t have different lengths. If they do, return False immediately.
2. Initialize Counter: Create an array of 26 integers, all set to 0. (Index 0 represents 'a', index 1 represents 'b', and so on).
3. Count Frequencies: Loop through the length of the strings.
   • Find the index for the character in s and add 1 to that position in the array.
   • Find the index for the character in t and subtract 1 from that position in the array.
4. Verify: Loop through the counter array. If you find any number that is not 0, it means the letters were unbalanced. Return False.
5. If all numbers are 0, return True.

5. Complexity Analysis

• Time Complexity: O(N) — We only traverse the strings once (where N is the length of the strings), and checking the array takes exactly 26 steps, which simplifies to O(1). Overall time is linear.
• Space Complexity: O(1) — We always use exactly an array of size 26, regardless of how long the input strings are. Since the memory footprint does not scale with the input size, it is constant space.

6. Code Implementations

Expand the sections below to see the optimal O(N) time and O(1) space implementation in your preferred programming language.

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        # If lengths differ, they can't be anagrams
        if len(s) != len(t):
            return False
            
        # Create a frequency array for the 26 lowercase English letters
        count = [0] * 26
        
        for i in range(len(s)):
            # ord(char) gets the ASCII value; subtract ord('a') to get index 0-25
            count[ord(s[i]) - ord('a')] += 1
            count[ord(t[i]) - ord('a')] -= 1
            
        # If any count is non-zero, the strings are not anagrams
        for c in count:
            if c != 0:
                return False
                
        return True

class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }
        
        int[] count = new int[26];
        
        for (int i = 0; i < s.length(); i++) {
            count[s.charAt(i) - 'a']++;
            count[t.charAt(i) - 'a']--;
        }
        
        for (int i = 0; i < count.length; i++) {
            if (count[i] != 0) {
                return false;
            }
        }
        
        return true;
    }
}

#include <string>
#include <vector>

class Solution {
public:
    bool isAnagram(std::string s, std::string t) {
        if (s.length() != t.length()) {
            return false;
        }
        
        int count[26] = {0};
        
        for (int i = 0; i < s.length(); i++) {
            count[s[i] - 'a']++;
            count[t[i] - 'a']--;
        }
        
        for (int i = 0; i < 26; i++) {
            if (count[i] != 0) {
                return false;
            }
        }
        
        return true;
    }
};

7. Conclusion: You Are Ready

You now understand how to optimize string comparisons. By realizing that the character set is limited (only 26 letters), you successfully traded a heavy O(N log N) sorting algorithm for a lightning-fast O(N) frequency array. This specific technique—mapping characters to a fixed-size array—is a powerful tool in your system design and algorithms arsenal. Trace the array increments and decrements on paper, and you will be completely prepared for this common interview question!