Jobs

Interviews

Discussions

Valid Anagram

Easy

Google

5 views

Topics:

Strings

Given two strings s and t, determine if t is an anagram of s. 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. 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^4
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

Google

5 views

Topics:

Strings

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^4
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? Should I treat uppercase and lowercase letters as distinct?
Can the input strings `s` and `t` contain characters outside the basic ASCII range (e.g., Unicode characters)?
Can the input strings `s` and `t` be empty or null?
Are spaces significant? Should I consider strings with different numbers of spaces as not anagrams?
Do you expect me to handle invalid input gracefully (e.g., by throwing an exception or returning a specific error value), or is it safe to assume the input will always be valid strings?

Brute Force Solution

Approach

The brute force way to check if two words are anagrams (meaning they contain the same letters, but in a different order) is to consider all possible arrangements of the letters in one word. Then, compare each arrangement with the other word to see if there's a match.

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

Take the first word.
Generate all the possible ways to rearrange the letters in that first word. Think of it like shuffling the letters around repeatedly to create different words.
For each of these rearranged words, compare it to the second word. Are they exactly the same?
If you find even one rearranged word from the first word that exactly matches the second word, then the words are anagrams.
If you've tried every single possible rearrangement of the first word and none of them match the second word, then they are not anagrams.

Code Implementation

def is_anagram_brute_force(first_string, second_string):
    # Function to generate all permutations of a string
    def find_all_permutations(input_string, current_permutation, all_permutations):
        if not input_string:
            all_permutations.append(''.join(current_permutation))
            return
        
        for index in range(len(input_string)):
            find_all_permutations(
                input_string[:index] + input_string[index+1:],
                current_permutation + [input_string[index]],
                all_permutations
            )

    # Generate all permutations of the first string
    all_possible_permutations = []

    # Need to start recursion with empty list
    find_all_permutations(first_string, [], all_possible_permutations)

    # Now we check if any permutation matches second string
    for permutation in all_possible_permutations:

        # If a match is found, strings are anagrams
        if permutation == second_string:
            return True

    # If no permutation matches, not anagrams
    return False

Big(O) Analysis

Time Complexity

O(n!) – The described brute force algorithm involves generating all permutations of the first word. If the length of the word is n, the number of possible permutations is n! (n factorial). For each of these n! permutations, we compare it with the second word, which takes O(n) time. Thus, the total time complexity is O(n! * n). Since n! dominates n, we can approximate the time complexity as O(n!).

Space Complexity

O(N!) – The brute force approach generates all possible permutations of the first word. The number of permutations for a word of length N is N! While it might be implemented recursively, the dominant space factor is storing those permutations. Therefore, the algorithm needs to hold up to N! arrangements of the first word at one time, each of length N, but typically space complexity focuses on the collection size, not the size of items within the collection. This yields an auxiliary space complexity of O(N!).

Optimal Solution

Approach

The goal is to efficiently determine if two words are anagrams of each other. A clever approach is to count the occurrences of each letter in both words and then compare the counts. If the counts are identical for all letters, the words are anagrams.

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

First, make sure both words have the same number of letters. If they don't, they can't be anagrams.
Next, create a tally of how many times each letter appears in the first word.
Then, go through the second word and subtract one from the tally for each letter we find.
Finally, check if every letter in our tally has a count of zero. If it does, the two words have the exact same letters and are anagrams.

Code Implementation

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

    # Use a dictionary to store character counts
    character_counts = {}

    for character in first_word:
        character_counts[character] = character_counts.get(character, 0) + 1

    # Decrement counts based on the second word
    for character in second_word:
        if character in character_counts:
            character_counts[character] -= 1
        else:
            return False

    # Check if all counts are zero
    # Meaning both words contain the same characters
    for count in character_counts.values():
        if count != 0:
            return False

    return True

Big(O) Analysis

Time Complexity

O(n) – The first step involves checking if the lengths of the two strings are equal, which takes constant time, O(1). Creating a frequency tally for the first word involves iterating through its 'n' characters. Subsequently, iterating through the second word to decrement the tally also takes 'n' steps. Finally, checking if all counts are zero involves iterating through the character counts (at most 26 for lowercase English letters), which is considered a constant time operation. Therefore, the overall time complexity is dominated by the two linear iterations through the input strings, resulting in O(n).

Space Complexity

O(1) – The provided solution uses a tally, which in the worst case would store a count for each distinct character in the input strings. Assuming the character set is fixed (e.g., ASCII with 128 characters or extended ASCII with 256 characters, or even Unicode with a larger, but still bounded, number of characters), the space used by the tally remains constant regardless of the input string length, N. Therefore, the space complexity is O(1) because the size of the tally does not scale with the input size N, it depends on the size of the character set which is considered constant.

Edge Cases

Case	How to Handle
Both input strings are empty	Return true, as empty strings can be considered anagrams of each other.
One string is empty, and the other is not	Return false, as an empty string cannot be an anagram of a non-empty string.
Input strings have different lengths	Return false immediately, as anagrams must have the same length.
Input strings are very long (e.g., 1 million characters)	The solution's time complexity should be O(n) or O(n log n) to handle large inputs efficiently, using a hash map or sorting.
Input strings contain unicode characters	The character counting mechanism (e.g., hash map) must support unicode characters correctly.
Input strings contain only one distinct character repeated many times, but with different counts (e.g., 'aaaa' and 'aaa')	The solution must correctly count the occurrences of each character to distinguish between these cases and return false.
Input strings are identical	Return true, as identical strings are anagrams of each other.
Input strings contain mixed case (e.g., 'Anagram' and 'anagram')	Convert both strings to lowercase or uppercase before comparison to ensure case-insensitive anagram detection.

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? Should I treat uppercase and lowercase letters as distinct?
Can the input strings `s` and `t` contain characters outside the basic ASCII range (e.g., Unicode characters)?
Can the input strings `s` and `t` be empty or null?
Are spaces significant? Should I consider strings with different numbers of spaces as not anagrams?
Do you expect me to handle invalid input gracefully (e.g., by throwing an exception or returning a specific error value), or is it safe to assume the input will always be valid strings?

Brute Force Solution

Approach

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

Take the first word.
Generate all the possible ways to rearrange the letters in that first word. Think of it like shuffling the letters around repeatedly to create different words.
For each of these rearranged words, compare it to the second word. Are they exactly the same?
If you find even one rearranged word from the first word that exactly matches the second word, then the words are anagrams.
If you've tried every single possible rearrangement of the first word and none of them match the second word, then they are not anagrams.

Code Implementation

def is_anagram_brute_force(first_string, second_string):
    # Function to generate all permutations of a string
    def find_all_permutations(input_string, current_permutation, all_permutations):
        if not input_string:
            all_permutations.append(''.join(current_permutation))
            return
        
        for index in range(len(input_string)):
            find_all_permutations(
                input_string[:index] + input_string[index+1:],
                current_permutation + [input_string[index]],
                all_permutations
            )

    # Generate all permutations of the first string
    all_possible_permutations = []

    # Need to start recursion with empty list
    find_all_permutations(first_string, [], all_possible_permutations)

    # Now we check if any permutation matches second string
    for permutation in all_possible_permutations:

        # If a match is found, strings are anagrams
        if permutation == second_string:
            return True

    # If no permutation matches, not anagrams
    return False

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

First, make sure both words have the same number of letters. If they don't, they can't be anagrams.
Next, create a tally of how many times each letter appears in the first word.
Then, go through the second word and subtract one from the tally for each letter we find.
Finally, check if every letter in our tally has a count of zero. If it does, the two words have the exact same letters and are anagrams.

Code Implementation

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

    # Use a dictionary to store character counts
    character_counts = {}

    for character in first_word:
        character_counts[character] = character_counts.get(character, 0) + 1

    # Decrement counts based on the second word
    for character in second_word:
        if character in character_counts:
            character_counts[character] -= 1
        else:
            return False

    # Check if all counts are zero
    # Meaning both words contain the same characters
    for count in character_counts.values():
        if count != 0:
            return False

    return True

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Both input strings are empty	Return true, as empty strings can be considered anagrams of each other.
One string is empty, and the other is not	Return false, as an empty string cannot be an anagram of a non-empty string.
Input strings have different lengths	Return false immediately, as anagrams must have the same length.
Input strings are very long (e.g., 1 million characters)	The solution's time complexity should be O(n) or O(n log n) to handle large inputs efficiently, using a hash map or sorting.
Input strings contain unicode characters	The character counting mechanism (e.g., hash map) must support unicode characters correctly.
Input strings contain only one distinct character repeated many times, but with different counts (e.g., 'aaaa' and 'aaa')	The solution must correctly count the occurrences of each character to distinguish between these cases and return false.
Input strings are identical	Return true, as identical strings are anagrams of each other.
Input strings contain mixed case (e.g., 'Anagram' and 'anagram')	Convert both strings to lowercase or uppercase before comparison to ensure case-insensitive anagram detection.