Valid Anagram problem and solution in Java and Python

Let’s go through the Valid Anagram problem step by step — with clear explanation, intuition, and code in Java and Python.

---

🧩 Problem: Valid Anagram

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

📘 Anagram means: You can rearrange the letters of one string to get the other string. For example:

• "listen" → "silent" ✅
• "triangle" → "integral" ✅
• "apple" → "pale" ❌ (because letters don’t match)

---

💡 Example

Input:  s = "anagram", t = "nagaram"
Output: true

Input:  s = "rat", t = "car"
Output: false

---

🧠 Intuition

To be anagrams:

• Both strings must have the same characters
• Each character must appear the same number of times

So, we can:

1. Count letters using a map or array.
2. Compare the counts.

---

🪜 Approach 1: Sorting (Simple and Clear)

🧩 Idea:

If two words are anagrams, sorting their letters will make them identical.

"anagram" → "aaagmnr"
"nagaram" → "aaagmnr" ✅

---

✅ Java Solution (Sorting)

import java.util.Arrays;

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

---

✅ Python Solution (Sorting)

def isAnagram(s: str, t: str) -> bool:
    return sorted(s) == sorted(t)

---

🧠 Approach 2: Counting (Optimized O(n))

🧩 Idea:

Instead of sorting, just count how many times each letter appears.

---

✅ Java Solution (Counting)

class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) return false;

        int[] count = new int[26]; // assuming only lowercase letters

        for (char c : s.toCharArray()) count[c - 'a']++;
        for (char c : t.toCharArray()) count[c - 'a']--;

        for (int n : count)
            if (n != 0) return false;

        return true;
    }
}

---

✅ Python Solution (Counting)

def isAnagram(s: str, t: str) -> bool:
    if len(s) != len(t):
        return False

    count = [0] * 26
    for ch in s:
        count[ord(ch) - ord('a')] += 1
    for ch in t:
        count[ord(ch) - ord('a')] -= 1

    return all(c == 0 for c in count)

---

🚀 Approach 3: Using HashMap (for any characters)

Useful if strings contain Unicode or mixed-case letters.

✅ Python

from collections import Counter

def isAnagram(s: str, t: str) -> bool:
    return Counter(s) == Counter(t)

✅ Java

import java.util.HashMap;

class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) return false;
        HashMap<Character, Integer> map = new HashMap<>();

        for (char c : s.toCharArray())
            map.put(c, map.getOrDefault(c, 0) + 1);

        for (char c : t.toCharArray()) {
            if (!map.containsKey(c)) return false;
            map.put(c, map.get(c) - 1);
            if (map.get(c) == 0) map.remove(c);
        }

        return map.isEmpty();
    }
}

---

⚖️ Complexity

Approach	Time	Space	Notes
Sorting	O(n log n)	O(1) or O(n)	Simple, short
Counting	O(n)	O(1)	Most efficient for lowercase
HashMap	O(n)	O(k)	Works for any charset

---