VALID ANAGRAM

Valid Anagram – Frequency Count Approach

Introduction

An anagram is a word or phrase formed by rearranging the letters of another word using all the original letters exactly once.

In this problem, we are given two strings and need to check whether one is an anagram of the other.

Problem Statement

Given two strings s and t, return:

  • true if t is an anagram of s

  • false otherwise

Example

Input:

s = "anagram"
t = "nagaram"

Output:

true

Solution Code

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

        int[] arr = new int[26];

        for (int i = 0; i < s.length(); i++) {
            arr[s.charAt(i) - 'a']++;
            arr[t.charAt(i) - 'a']--;
        }

        for (int check : arr) {
            if (check != 0)
                return false;
        }

        return true;
    }
}

Approach Used: Frequency Counting

Idea

If two strings are anagrams:

  • They must have the same characters

  • Each character must appear the same number of times

How It Works

  1. Check lengths:

    • If lengths are different = return false

  2. Create an array of size 26:

    • Each index represents a letter (a–z)

  3. Traverse both strings:

    • Increment count for characters in s

    • Decrement count for characters in t

  4. Check the array:

    • If all values are 0 = strings are anagrams

    • Otherwise = not anagrams

Why This Approach Was Chosen

  • Very efficient (single traversal)

  • No need for sorting

  • Uses fixed-size array = constant space

  • Faster than comparing sorted strings

Alternative Approaches

  • Sorting both strings

    sort(s) == sort(t)

     Time Complexity: O(n log n)

  • Using HashMap
     Works for all characters
     Slightly more space

Why frequency array?
Because input contains only lowercase letters → most efficient choice

Time and Space Complexity

  • Time Complexity: O(n)

  • Space Complexity: O(1) (fixed array of size 26)

Follow-Up: Unicode Characters

If the strings contain Unicode characters:

  • We cannot use a fixed array of size 26

Modified Approach:

  • Use a HashMap

Map<Character, Integer> map = new HashMap<>();

Why?

  • Unicode has a large range of characters

  • HashMap handles dynamic character sets

Important Observation

  • Incrementing and decrementing in the same loop reduces work

  • Final check ensures all counts balance to zero

Conclusion

The frequency count approach is an efficient and elegant way to check for anagrams. It avoids sorting and works in linear time, making it ideal for large inputs. For extended character sets like Unicode, the approach can be adapted using a HashMap.


Comments

Post a Comment

Popular posts from this blog

THE DELIVERY MAN

  The Delivery Man – Python List Operations  Introduction Lists in Python are used to store multiple items in a single variable. They are flexible, allowing us to add, remove, update, and manipulate elements easily. In this task, different list operations are performed to simulate a delivery man's workflow. 1. Creating a list and accessing an item items = ["Notebook", "Pencil", "Eraser", "Ruler", "Marker"] print(items[2]) Approach: Indexing Why: Lists use zero-based indexing, so the third item is accessed using index 2. 2. Adding a new item items.append("Glue Stick") print(items) Approach: append() method Why: It adds an item at the end of the list, which is ideal for adding new deliveries. 3. Inserting an item items.insert(2, "Highlighter") print(items) Approach: insert() method Why: Used when we need to add an item at a specific position instead of the end. 4. Removing an item items.remove("Ruler...
Read more

EC2 LAUNCHING

  EC2 Step 1: Launch EC2 Instance Go to: AWS Console --> EC2 --> Launch Instance Configure: Name : my-web-server AMI : Amazon Linux 2 (easy for beginners) Instance Type : t2.micro (free tier) Step 2: Key Pair Create or select a key pair. Step 3: Network Settings  Allow these: SSH (port 22) --> for login  HTTP (port 80) --> for web access Step 4: Launch Instance Click Launch Instance Step 5: Connect to Instance Use: EC2 --> Connect --> EC2 Instance Connect (easiest) OR via terminal: with this command. for this you have to download the pem files while selecting the key pair.  ssh -i your-key.pem ec2-user@<public-ip> Step 6: Install Web Server For Amazon Linux: sudo yum update -y sudo yum install httpd -y Step 7: Start Web Server sudo systemctl start httpd sudo systemctl enable httpd Step 8: Add a Web Page echo "Hello from EC2" | sudo tee /var/www/html/index.html Step 9: Get Public IP Go to EC2 d...
Read more

SORT A LINKED LIST USING MERGE SORT

  Sort a Linked List using Merge Sort Introduction Sorting a linked list efficiently is a common problem in data structures. Unlike arrays, linked lists do not allow direct access to elements, so algorithms like quicksort are not ideal. Merge Sort is the best choice for linked lists because: It does not require random access It works efficiently with node-based structures Problem Statement Given the head of a linked list: Sort the list in ascending order Return the sorted linked list Example Input: 10 -> 30 -> 20 -> 40 -> 60 -> 50 Output: 10 -> 20 -> 30 -> 40 -> 50 -> 60 Solution Code class Solution: def mergeSort(self, head): if not head or not head.next: return head mid = self.getMiddle(head) next_to_mid = mid.next mid.next = None left = self.mergeSort(head) right = self.mergeSort(next_to_mid) return self.merge(left, right) def getMiddle(self,...
Read more