Problem 38 - Valid Anagram

Explore our archive for previous posts.

Problem 37 - Contains Duplicate II

Problem 36 - Contains Duplicate

Question

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

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.

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.

Approach

The approach for solving this problem involves comparing two strings, s and t, to determine if they are anagrams. To do this, we create a character count array to track the frequency of each character in s. We iterate through both strings, updating the character count array based on the characters in s and decrementing it based on characters in t. If the character count array is zero for all characters at the end, it means s and t are anagrams, and we return true.

Solution

Solve it here

class Solution {
    public boolean isAnagram(String s, String t) {
        // Check if the input strings are of different lengths
        if (s.length() != t.length()) {
            return false; // If lengths differ, they cannot be anagrams
        }
        
        // Create an array to count the occurrences of each character
        int[] charCount = new int[26]; // Assuming lowercase English alphabet
        
        // Iterate through the first string, incrementing counts
        for (char ch : s.toCharArray()) {
            charCount[ch - 'a']++;
        }
        
        // Iterate through the second string, decrementing counts
        for (char ch : t.toCharArray()) {
            charCount[ch - 'a']--;
        }
        
        // If the two strings are anagrams, all counts should be zero
        for (int count : charCount) {
            if (count != 0) {
                return false; // If any count is not zero, they are not anagrams
            }
        }
        
        return true; // All character counts are zero, so they are anagrams
    }
}

Time and space complexity

Time Complexity: The solution iterates through both strings once, so the time complexity is O(n), where 'n' is the length of the strings.

Space Complexity: The space complexity is O(1) because the count array has a constant size of 26, which doesn't depend on the length of the input strings.

Explore more?

Missed a previous edition? Catch up on the insightful content you might have missed by visiting our archive here. Thank you for being a valued reader of our newsletter. We appreciate your continued support!