Problem Statement #

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

Examples #

Example 1:

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

Example 2:

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

Solution #

var isAnagram = function(s, t) {
    let s1 = s.split('');
    let s2 = t.split('');
    
    // Sort arrays
    s1 = s1.sort();
    s2 = s2.sort();
    
    console.log(s1);
    console.log(s2);
    
    // Compare arrays
    for (let i = 0; i < s1.length; i++) {
        if (s1[i] != s2[i]) {
            return false;
        }
    }
    
    // If different lengths
    if (s1.length != s2.length) {
        return false;
    }
    
    return true;
};

Understanding Anagrams #

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. In other words, two strings are anagrams if they contain the same characters with the same frequencies, just in a different order.

Examples of Anagrams #

✓ "anagram" and "nagaram" are anagrams
  You can rearrange "anagram" to form "nagaram"

✗ "rat" and "cat" are NOT anagrams
  "rat" doesn't contain the letter 'c'

Approach Analysis #

Key Insight: Length Check #

If two strings have different lengths, they cannot be anagrams. This is because anagrams must use all original letters exactly once. A longer string would have leftover characters that couldn’t be matched in the shorter string.

Sort and Compare Method #

The primary approach used in this solution is the sort and compare method:

1. Split both strings into character arrays
2. Sort both arrays alphabetically
3. Compare the sorted arrays element by element
4. Verify that both arrays have the same length

This approach has a time complexity of O(n log n) due to the sorting operation. While the comparison loop is O(n), the sorting dominates the overall complexity, resulting in O(n log n).

Alternative Approach: Character Counting #

Another viable approach is to use a hash map (object) to count character frequencies:

1. Create a frequency map for the first string
2. Create a frequency map for the second string
3. Compare the two frequency maps

This alternative approach has a time complexity of O(n) and space complexity of O(1) (assuming a fixed character set like lowercase English letters, which has at most 26 unique characters).

When to use character counting over sorting:

The character counting method becomes particularly advantageous when:

• You need to compare one string against multiple other strings
• You’re working with very long strings (e.g., 2,000+ characters)
• You want optimal time complexity

For example, if you have a 2,000-character string and need to check it against multiple candidates, you only need to create the frequency map once and then compare it against each candidate’s frequency map. This means comparing at most 26-52 character counts instead of iterating through 2,000 characters for each comparison.

In the current solution, since we’re only comparing two strings once, the simpler sort-and-compare approach is perfectly acceptable and more straightforward to implement.

Code Breakdown #

Let’s examine each section of the solution in detail:

Step 1: Split Strings into Arrays #

let s1 = s.split('');
let s2 = t.split('');

The split('') method with an empty string argument separates each character into its own element in an array. For example:

• "anagram".split('') produces ['a', 'n', 'a', 'g', 'r', 'a', 'm']

Step 2: Sort the Arrays #

s1 = s1.sort();
s2 = s2.sort();

The sort() function, when called without a callback function, performs a default lexicographic (alphabetical/numerical) sort. For strings containing only letters, this works perfectly.

Important note: JavaScript’s default sort can produce unexpected results with numbers stored as strings (e.g., ['10', '2', '3'].sort() gives ['10', '2', '3'] instead of ['2', '3', '10']). For more complex sorting scenarios, always provide a custom comparison callback function. However, for this problem with letter-only strings, the default behavior is exactly what we need.

After sorting:

• ['a', 'n', 'a', 'g', 'r', 'a', 'm'] becomes ['a', 'a', 'a', 'g', 'm', 'n', 'r']
• ['n', 'a', 'g', 'a', 'r', 'a', 'm'] becomes ['a', 'a', 'a', 'g', 'm', 'n', 'r']

Step 3: Compare Arrays Element by Element #

for (let i = 0; i < s1.length; i++) {
    if (s1[i] != s2[i]) {
        return false;
    }
}

This loop iterates through the first array and compares each element with the corresponding element in the second array. If any mismatch is found, we immediately return false because the strings cannot be anagrams.

This comparison works correctly when:

• Both arrays are the same length
• The first array is shorter (it will catch mismatches)
• The first array is longer (it will eventually compare with undefined in the second array and return false)

However, there’s a subtle edge case when the second array is longer than the first…

Step 4: Verify Equal Lengths #

if (s1.length != s2.length) {
    return false;
}

This check is crucial for correctness. Here’s why:

The previous loop only iterates through s1.length elements. If s2 is longer than s1, the loop will complete without checking the additional elements in s2. For example:

• s1 = ['a', 'b']
• s2 = ['a', 'b', 'c']

The loop would compare indices 0 and 1, find them equal, and exit without catching that s2 has an extra ‘c’. Without the length check, the function would incorrectly return true.

By verifying that both arrays have the same length, we ensure that our element-by-element comparison is comprehensive and accounts for all characters.

Step 5: Return True #

return true;

If we’ve made it past all the checks without returning false, then the strings are indeed anagrams, and we return true.

Time and Space Complexity #

Time Complexity: O(n log n) #

The time complexity is dominated by the sorting operation:

• split(): O(n) - creates an array with n elements
• sort(): O(n log n) - JavaScript typically uses an optimized sorting algorithm like Timsort
• Loop comparison: O(n) - iterates through n elements
• Length check: O(1) - constant time

Overall: O(n) + O(n log n) + O(n) + O(1) = O(n log n)

Space Complexity: O(n) #

We create two new arrays to hold the characters from both strings, each of size n (or close to it), resulting in O(n) space complexity.

Potential Optimizations #

1. Early length check: Move the length check to the beginning to fail fast if the strings have different lengths
2. Character frequency map: Use the O(n) hash map approach for better time complexity
3. Use strict equality: Change != to !== for better practice (though it doesn’t affect this particular case)

Optimized Version with Early Length Check #

var isAnagram = function(s, t) {
    // Early return if lengths differ
    if (s.length !== t.length) {
        return false;
    }
    
    let s1 = s.split('').sort();
    let s2 = t.split('').sort();
    
    for (let i = 0; i < s1.length; i++) {
        if (s1[i] !== s2[i]) {
            return false;
        }
    }
    
    return true;
};

This optimization avoids unnecessary splitting and sorting operations when we can immediately determine the strings cannot be anagrams.

Conclusion #

The Valid Anagram problem is an excellent exercise for understanding string manipulation, array operations, and algorithmic complexity. The sort-and-compare approach provides a clean, intuitive solution that’s easy to understand and implement, making it perfect for interview situations where clarity of thought is important.

While there are more optimal solutions in terms of time complexity (like the hash map approach), the O(n log n) solution presented here is perfectly acceptable for most practical scenarios and demonstrates strong fundamentals in algorithm design. 🙂