2.Valid Anagram

Here’s a list of all approaches for solving the “Valid Anagram” problem in Java, from brute force to optimal solutions. The problem is typically stated as:

Problem:
Given two strings, s and t, return true if t is an anagram of s, and false otherwise.
An anagram is formed by rearranging the letters of one string to match another, where the frequency of characters must match exactly.

---

1. Brute Force Approach – O(n²)

Logic: Compare each character from s to t and remove characters from t if they match.

• For each character in s, loop through t and check for a match. Remove the matching character if found.

Time Complexity: O(n²) (due to nested loops)
Space Complexity: O(n) (since t is modified to remove matching characters)

Java Code:

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

        StringBuilder tBuilder = new StringBuilder(t);
        for (char c : s.toCharArray()) {
            int index = tBuilder.indexOf(String.valueOf(c));  // Find the matching character in 't'
            if (index != -1) {
                tBuilder.deleteCharAt(index);  // Remove the character from 't'
            } else {
                return false;  // If a character doesn't match, it's not an anagram
            }
        }
        return true;  // If all characters match, it's an anagram
    }

    public static void main(String[] args) {
        System.out.println(isAnagram("listen", "silent"));  // Output: true
        System.out.println(isAnagram("hello", "world"));    // Output: false
    }
}

---

2. Sorting Approach – O(n log n)

Logic: Sort both strings and check if they are equal.

• If two strings are anagrams, their sorted versions should be the same.

Time Complexity: O(n log n) (for sorting)
Space Complexity: O(n) (for storing the sorted arrays)

Java Code:

import java.util.Arrays;

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

        char[] sArray = s.toCharArray();
        char[] tArray = t.toCharArray();

        Arrays.sort(sArray);
        Arrays.sort(tArray);

        return Arrays.equals(sArray, tArray);  // Check if sorted arrays are identical
    }

    public static void main(String[] args) {
        System.out.println(isAnagram("listen", "silent"));  // Output: true
        System.out.println(isAnagram("hello", "world"));    // Output: false
    }
}

---

3. HashMap Approach (Frequency Count) – O(n)

Logic: Use a HashMap to count the frequency of characters in both strings.

• First, count character frequencies for s and store them in a map.
• Then, decrement the count for each character in t. If any frequency goes below zero, it’s not an anagram.

Time Complexity: O(n)
Space Complexity: O(n)

Java Code:

import java.util.HashMap;

public class ValidAnagramHashMap {
    public static 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);  // Count frequencies in 's'
        }

        for (char c : t.toCharArray()) {
            if (!map.containsKey(c) || map.get(c) == 0) return false;  // Character mismatch
            map.put(c, map.get(c) - 1);  // Decrement frequency
        }
        return true;
    }

    public static void main(String[] args) {
        System.out.println(isAnagram("listen", "silent"));  // Output: true
        System.out.println(isAnagram("hello", "world"));    // Output: false
    }
}

---

4. Optimal Approach (Using Array Frequency Count) – O(n)

Logic: Use an integer array of size 26 to store character counts.

• Increment counts for characters in s and decrement for characters in t.
• If the final array has all zeros, then s and t are anagrams.

Time Complexity: O(n)
Space Complexity: O(1) (since the array size is fixed at 26)

Java Code:

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

        int[] charCounts = new int[26];  // Array to store counts for 'a' to 'z'
        for (int i = 0; i < s.length(); i++) {
            charCounts[s.charAt(i) - 'a']++;  // Increment for 's'
            charCounts[t.charAt(i) - 'a']--;  // Decrement for 't'
        }

        for (int count : charCounts) {
            if (count != 0) return false;  // If any count is non-zero, not an anagram
        }
        return true;  // All counts are zero, so it's an anagram
    }

    public static void main(String[] args) {
        System.out.println(isAnagram("listen", "silent"));  // Output: true
        System.out.println(isAnagram("hello", "world"));    // Output: false
    }
}

---

5. Using Java Streams (Optional Functional Approach)

Logic: Use Java Streams to count character frequencies and compare maps.

Time Complexity: O(n)
Space Complexity: O(n)

Java Code:

import java.util.stream.Collectors;

public class ValidAnagramStreams {
    public static boolean isAnagram(String s, String t) {
        return s.length() == t.length() &&
               s.chars().boxed().collect(Collectors.groupingBy(c -> c, Collectors.counting()))
               .equals(t.chars().boxed().collect(Collectors.groupingBy(c -> c, Collectors.counting())));
    }

    public static void main(String[] args) {
        System.out.println(isAnagram("listen", "silent"));  // Output: true
        System.out.println(isAnagram("hello", "world"));    // Output: false
    }
}

---

Summary of Approaches and Complexities:

Approach	Time Complexity	Space Complexity	Description
Brute Force	O(n²)	O(n)	Compare each char and modify t string
Sorting-Based	O(n log n)	O(n)	Sort and compare both strings
HashMap (Frequency Count)	O(n)	O(n)	Count char frequencies in both strings
Array Frequency (Optimal)	O(n)	O(1)	Use fixed-size array to store counts
Java Streams (Functional)	O(n)	O(n)	Compare frequency maps using streams

---

Best Approach Recommendation:

The Array Frequency Count Approach (Optimal) is usually the best in terms of efficiency and simplicity, with O(n) time and O(1) space complexity. If you’re looking for modern, concise code, the Java Streams Approach is also a good option.