Solving Valid Anagram

Valid Anagram is a common interview question that is often used to assess a candidate's understanding of string manipulation and data structures. The problem asks whether two given strings are anagrams of each other, meaning that they contain the same letters in the same frequency, but in a different order.

It may seem like a simple problem at first, but there are several ways to approach it and optimize the solution, making it a great exercise in problem-solving and critical thinking.

The Premise

An anagram is a word or phrase formed by rearranging the letters of another, such as "listen" and "silent". In this question, we are given two strings and we need to check if they are anagrams of each other.

Noob Solution

One of the first intuitive solutions to this problem is to sort both strings and compare them to see if they are the same. If they are the same, then they are anagrams of each other.

Here is the code:

In JS:

const isAnagram = (s, t) => {
    if (s.length !== t.length) {
        return false;
    }

    const sSorted = s.split("").sort().join("");
    const tSorted = t.split("").sort().join("");

    return sSorted === tSorted;
}

In Python:

def isAnagram(s: str, t: str) -> bool:
    if len(s) != len(t):
        return False

    s_sorted = "".join(sorted(s))
    t_sorted = "".join(sorted(t))

    return s_sorted == t_sorted

This code checks if two strings are anagrams of each other by comparing their sorted versions.

If the lengths of the strings are different, it immediately returns false, as anagrams must have the same length.

Otherwise, it sorts the two strings and compares them. If they are the same, then the original strings are anagrams.

Pro Solution

While this solution is correct, it is not the most efficient as it has a time complexity of O(n log n) due to the sorting step. We can optimize this solution by using a hash table to count the number of occurrences of each character in both strings. If the number of occurrences of each character is the same in both strings, then they are anagrams of each other.

Here is the code:

In JS:

const isAnagram = (s, t) => {
    if (s.length !== t.length) {
        return false;
    }

    const charCount = {};

    for (let i = 0; i < s.length; i++) {
        const char = s[i];
        charCount[char] = charCount[char] ? charCount[char] + 1 : 1;
    }

    for (let i = 0; i < t.length; i++) {
        const char = t[i];
        if (!charCount[char]) {
            return false;
        }
        charCount[char]--;
    }

    return true;
}

In Python:

def isAnagram(s: str, t: str) -> bool:
    if len(s) != len(t):
        return False

    char_count = {}

    for char in s:
        if char in char_count:
            char_count[char] += 1
        else:
            char_count[char] = 1

    for char in t:
        if char not in char_count or char_count[char] == 0:
            return False
        char_count[char] -= 1

    return True

This solution has a time complexity of O(n) as it requires iterating over each string only once to count the number of occurrences of each character.

Conclusion

The valid anagram question is useful because it is a common problem that arises in various fields such as computer science, linguistics, and cryptography.

In computer science, anagrams are used in various applications such as spell checkers, word games, and search algorithms. Anagrams also play a significant role in cryptography, where the letters of a message are rearranged to form a secret code.

Additionally, understanding anagrams can help with language acquisition and literacy development by improving vocabulary and spelling skills. Therefore, the ability to determine whether two strings are valid anagrams is an important skill for developers, linguists, and anyone interested in language and cryptography.