Jobs

Interviews

Discussions

Valid Anagram

Easy

Atlassian

0 views

Topics:

ArraysStrings

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

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.

Follow up: What if the inputs contain Unicode characters? How would you adapt your solution to such a case?

Valid Anagram

Easy

Atlassian

0 views

Topics:

ArraysStrings

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

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.

Follow up: What if the inputs contain Unicode characters? How would you adapt your solution to such a case?

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Are the input strings `s` and `t` case-sensitive? For example, should "Anagram" and "anagram" be considered anagrams?
Can the input strings `s` and `t` contain characters outside the ASCII range, such as Unicode characters?
Are the input strings `s` and `t` allowed to be empty or null?
What is the maximum length of the input strings `s` and `t`? Is there a specific range I should be aware of?
Should I consider whitespace characters when determining if the strings are anagrams?

Brute Force Solution

Approach

The brute force way to check if two words are anagrams is to try out every possible combination of letters from the first word and see if we can rearrange them to match the second word. It is like blindly trying every possibility until we find a match, or we run out of options.

Here's how the algorithm would work step-by-step:

First, check if both words have the same number of letters. If they don't, they can't be anagrams, so we're done.
Next, think of taking each letter from the first word, one by one.
For each letter, look at the second word. Try to find the exact same letter in the second word.
If you find a match, remove that letter from the second word and move on to the next letter in the first word.
If you can't find the letter, then the words are not anagrams, and we're done.
Repeat steps 3-5 for all letters in the first word.
If, after going through every letter in the first word, the second word is empty (all letters were matched and removed), then the two words are anagrams.

Code Implementation

def is_anagram_brute_force(first_word, second_word):
    # Anagrams must have equal length
    if len(first_word) != len(second_word):
        return False

    second_word_list = list(second_word)

    for first_word_character in first_word:
        character_found = False
        for second_word_index in range(len(second_word_list)):
            # Attempt to find character match in second_word_list
            if first_word_character == second_word_list[second_word_index]:
                second_word_list.pop(second_word_index)
                character_found = True
                break

        # Return False if no character in the first word is found
        if not character_found:
            return False

    # Words are anagrams if second_word_list is now empty
    if not second_word_list:
        return True
    else:
        return False

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through each of the n characters in the first string. For each character, it searches for a matching character in the second string, which takes up to n operations. Removing a character from the second string (e.g., using slicing or similar methods) within the inner loop also takes O(n) time. Thus, for each of the n characters in the first word, we potentially perform n comparisons and an n removal operation. Therefore, this results in approximately n * (n + n) which simplifies to O(n²).

Space Complexity

O(N) – The algorithm modifies the second word by removing letters. In the worst-case scenario, to avoid modifying the original input, we might make a copy of the second word. This would require creating a temporary data structure (e.g., a list or string) to hold the characters of the second word, with its size proportional to the number of characters in the word. Thus, we require extra space proportional to the size of the second word; let's define N as the length of the second word, then space used is N. Therefore, the space complexity is O(N).

Optimal Solution

Approach

To determine if two words are anagrams of each other, we will count how many times each letter appears in each word. If the counts are identical for both words, then they are anagrams.

Here's how the algorithm would work step-by-step:

First, check if the words have the same number of letters. If they don't, they can't be anagrams.
Create a system to count how many times each letter appears in the first word.
Use the same system to count how many times each letter appears in the second word.
Compare the letter counts from both words. If all the letter counts match, the words are anagrams. If any count is different, they are not anagrams.

Code Implementation

def are_anagrams(first_word, second_word):
    if len(first_word) != len(second_word):
        return False

    # Use a dictionary to store letter counts for the first word.
    first_word_letter_counts = {}
    for letter in first_word:
        first_word_letter_counts[letter] = first_word_letter_counts.get(letter, 0) + 1

    # Use a dictionary to store letter counts for the second word.
    second_word_letter_counts = {}
    for letter in second_word:
        second_word_letter_counts[letter] = second_word_letter_counts.get(letter, 0) + 1

    # Check that the character counts are identical.
    if first_word_letter_counts == second_word_letter_counts:
        return True

    return False

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n) – The described algorithm's time complexity is determined by the length of the input strings, which we can denote as 'n'. The initial length check is O(1). Counting letter frequencies in each word iterates through the string once, resulting in O(n) complexity for each word. Comparing the letter counts also iterates through, at most, the unique letters in the string, which is bound by n, giving a maximum of O(n). Thus, the operations are O(1) + O(n) + O(n) + O(n), which simplifies to O(n).

Space Complexity

O(1) – The algorithm creates a system, implicitly a hash map or array, to count letter occurrences in both words. In the worst case, each distinct character in the input words will be stored in the counting system. Since the number of possible characters is limited (e.g., 26 for lowercase English letters), the size of this counting system is constant regardless of the input word length. Thus, the space complexity remains constant.

Edge Cases

Case	How to Handle
s or t is null	Return false immediately as null strings cannot be anagrams.
s or t is empty string	If both are empty, return true; if only one is, return false.
s and t have different lengths	Return false immediately since anagrams must have equal length.
s and t are identical strings	Should return true because a string is an anagram of itself.
s and t contain unicode characters	The character frequency map should support unicode characters correctly.
s and t contain only a few distinct characters, but many repetitions of each.	Frequency counter approach should still work efficiently in this scenario.
Very large strings that may cause integer overflow in frequency counting if not using a large enough data type.	Use a data type for frequency counting (e.g., int, long) large enough to avoid overflow.
Strings with mixed case characters ('a' vs 'A')	Convert both strings to lowercase or uppercase before comparing frequencies.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Are the input strings `s` and `t` case-sensitive? For example, should "Anagram" and "anagram" be considered anagrams?
Can the input strings `s` and `t` contain characters outside the ASCII range, such as Unicode characters?
Are the input strings `s` and `t` allowed to be empty or null?
What is the maximum length of the input strings `s` and `t`? Is there a specific range I should be aware of?
Should I consider whitespace characters when determining if the strings are anagrams?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

First, check if both words have the same number of letters. If they don't, they can't be anagrams, so we're done.
Next, think of taking each letter from the first word, one by one.
For each letter, look at the second word. Try to find the exact same letter in the second word.
If you find a match, remove that letter from the second word and move on to the next letter in the first word.
If you can't find the letter, then the words are not anagrams, and we're done.
Repeat steps 3-5 for all letters in the first word.
If, after going through every letter in the first word, the second word is empty (all letters were matched and removed), then the two words are anagrams.

Code Implementation

def is_anagram_brute_force(first_word, second_word):
    # Anagrams must have equal length
    if len(first_word) != len(second_word):
        return False

    second_word_list = list(second_word)

    for first_word_character in first_word:
        character_found = False
        for second_word_index in range(len(second_word_list)):
            # Attempt to find character match in second_word_list
            if first_word_character == second_word_list[second_word_index]:
                second_word_list.pop(second_word_index)
                character_found = True
                break

        # Return False if no character in the first word is found
        if not character_found:
            return False

    # Words are anagrams if second_word_list is now empty
    if not second_word_list:
        return True
    else:
        return False

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

To determine if two words are anagrams of each other, we will count how many times each letter appears in each word. If the counts are identical for both words, then they are anagrams.

Here's how the algorithm would work step-by-step:

First, check if the words have the same number of letters. If they don't, they can't be anagrams.
Create a system to count how many times each letter appears in the first word.
Use the same system to count how many times each letter appears in the second word.
Compare the letter counts from both words. If all the letter counts match, the words are anagrams. If any count is different, they are not anagrams.

Code Implementation

def are_anagrams(first_word, second_word):
    if len(first_word) != len(second_word):
        return False

    # Use a dictionary to store letter counts for the first word.
    first_word_letter_counts = {}
    for letter in first_word:
        first_word_letter_counts[letter] = first_word_letter_counts.get(letter, 0) + 1

    # Use a dictionary to store letter counts for the second word.
    second_word_letter_counts = {}
    for letter in second_word:
        second_word_letter_counts[letter] = second_word_letter_counts.get(letter, 0) + 1

    # Check that the character counts are identical.
    if first_word_letter_counts == second_word_letter_counts:
        return True

    return False

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
s or t is null	Return false immediately as null strings cannot be anagrams.
s or t is empty string	If both are empty, return true; if only one is, return false.
s and t have different lengths	Return false immediately since anagrams must have equal length.
s and t are identical strings	Should return true because a string is an anagram of itself.
s and t contain unicode characters	The character frequency map should support unicode characters correctly.
s and t contain only a few distinct characters, but many repetitions of each.	Frequency counter approach should still work efficiently in this scenario.
Very large strings that may cause integer overflow in frequency counting if not using a large enough data type.	Use a data type for frequency counting (e.g., int, long) large enough to avoid overflow.
Strings with mixed case characters ('a' vs 'A')	Convert both strings to lowercase or uppercase before comparing frequencies.