We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Valid Anagram

Number: 242

Difficulty: Easy

Paid? No

Companies: Bloomberg, Google, Amazon, Meta, Microsoft, Affirm, Apple, Oracle, Infosys, American Express, tcs, BlackRock, Cognizant, TikTok, EPAM Systems, Adobe, Goldman Sachs, PayPal, Yandex, Uber, Spotify, J.P. Morgan, Siemens, Autodesk, Fidelity, Yelp

Problem Description

Given two strings s and t, determine if t is an anagram of s. In other words, check whether t can be rearranged to form s. Both s and t consist of lowercase English letters.

Key Insights

  • If s and t have different lengths, they cannot be anagrams.
  • An anagram requires exactly the same character frequency for both strings.
  • Using a hash table (or frequency array when limited to 26 lowercase letters) provides an efficient solution.
  • An alternative approach is to sort both strings and compare them.
  • For Unicode inputs, a hash table is more adaptable than a fixed-size frequency array.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the strings (using a hash table for counting).
Space Complexity: O(1) if we use a fixed-size array (for 26 letters), otherwise O(n) for a hash table with a larger character set.

Solution

We use a hash table (dictionary) to count the frequency of each character in the first string s. Then, we iterate over string t and decrement the count for each character. If at any point a character count goes negative or a character is missing in the hash table, t cannot be an anagram of s. Finally, if all counts return to zero, the strings are anagrams. This approach is efficient and handles the problem in linear time.

Code Solutions

# Python solution for Valid Anagram

def isAnagram(s: str, t: str) -> bool:
    # Check if lengths differ; if so, they can't be anagrams
    if len(s) != len(t):
        return False

    # Create a dictionary to count frequency of each character in s
    char_count = {}
    for char in s:
        # Increase the count of the character
        char_count[char] = char_count.get(char, 0) + 1

    # Decrease the count for each character in t
    for char in t:
        if char not in char_count or char_count[char] == 0:
            # Character not found or count mismatch, not an anagram
            return False
        char_count[char] -= 1

    # If all counts are zero, it's a valid anagram
    return True

# Example usage:
print(isAnagram("anagram", "nagaram"))  # Output: True
print(isAnagram("rat", "car"))          # Output: False
← Back to All Questions