Valid Anagram

EASY

Description

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?

Approaches

Checkout 2 different approaches to solve Valid Anagram. Click on different approaches to view the approach and algorithm in detail.

Sorting Approach

Sort both strings and compare them character by character. If they are equal, then they are anagrams.

Algorithm

Check if lengths of both strings are equal
Convert strings to char arrays
Sort both arrays
Compare sorted arrays

This approach involves sorting both strings and then comparing them. If two strings are anagrams, they will be equal after sorting.

public boolean isAnagram(String s, String t) {
    if (s.length() != t.length()) {
        return false;
    }
    
    char[] str1 = s.toCharArray();
    char[] str2 = t.toCharArray();
    
    Arrays.sort(str1);
    Arrays.sort(str2);
    
    return Arrays.equals(str1, str2);
}

First, we check if the lengths of both strings are equal. If not, they cannot be anagrams. Then, we convert both strings to character arrays and sort them. Finally, we compare the sorted arrays. If they are equal, the strings are anagrams.

Complexity Analysis

Time Complexity: O(n log n) where n is the length of the strings (due to sorting)Space Complexity: O(n) where n is the length of the strings (for creating char arrays)

Pros and Cons

Pros:

Simple to implement
Easy to understand
Works with Unicode characters without modification

Cons:

Not the most efficient solution
Modifies the original strings
Requires extra space for sorting

Code Solutions

Checking out 5 solutions in different languages for Valid Anagram. Click on different languages to view the code.

public class Solution {
    public bool IsAnagram(string s, string t) {
        if (s.Length != t.Length) {
            return false;
        }
        int[] cnt = new int[26];
        for (int i = 0; i < s.Length; ++i) {
            ++cnt[s[i] - 'a'];
            --cnt[t[i] - 'a'];
        }
        return cnt.All(x => x == 0);
    }
}

Video Solution

Watch the video walkthrough for Valid Anagram

Algorithms:

Sorting

Data Structures:

Hash TableString

Companies:

Accenture |American Express |Atlassian |Capgemini |