242. Valid Anagram.md

Valid Anagram

See Problem on LeetCode

Problem Description

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, 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.

My Solution

(EASY) Java

class Solution {
    public boolean isAnagram(String s, String t) {
        // two strings 
        // t is an anagram of s
        // contains
        // if one of the letters isnt in at all we stop
        // all must be in

        // first check
        // if s.length == t.length 
        // immediately return false if not

        // check two
        // loop through 't'
        // the comparison****
        // lets start

        if (s.length() != t.length()) {
            return false;
        } 

        // frequency array fot lowercase characters
        int[] charCount = new int[26];

        // frequency counting approach
        for (int i = 0; i < t.length(); i++) {
            charCount[s.charAt(i) - 'a']++;   // increment count fot s
            charCount[t.charAt(i) - 'a']--;   // decrement count fot t
        }

        // check if all counts are zero
        for (int count : charCount) {
            if (count != 0) {
                return false;
            }
        }
        return true;
    }
}

Runtime: 5 ms | BEATS: 53.03%
Memory: 42.91 MB | BEATS: 80.60%
Time Complexity: O(N)
Space Complexity: O(1)

How I approached it:

Intuition:

1. Frequency Count: Since an anagram has the same characters with the same frequency, a simple frequency count for each character in the strings is sufficient to verify this.

2. Efficient Frequency Comparison: As we loop through both strings simultaneously, we increment and decrement the frequency of characters in a fixed-size array, which simplifies the comparison.

Algorithm Explanation:

How I really went about it:

1. Length Check:

   • If the lengths of s and t are not the same, immediately return false since they can't be anagrams.

2. Frequency Array:

   • Initialize an array charCount of size 26 to track the frequency of each character (from 'a' to 'z').

3. Count Characters:

   • Loop through each character in both s and t.
   • Increment the count for characters in s.
   • Decrement the count for characters in t.

4. Final Check:

   • After processing both strings, check if all counts in charCount are zero.
   • If any count is not zero, it means the strings do not have matching characters in the correct frequency.

Complexity Analysis:

• Time Complexity: O(N)

  • We traverse both strings once, where N is the length of the strings.

• Space Complexity: O(1)

  • The space is constant since the frequency array size is fixed at 26.

Performance:

• Runtime: 5 ms, faster than 53.03% of submissions.
• Memory Usage: 42.91 MB, beating 80.60% of submissions.