Valid Anagrams

Introduction

Language, with its intricate patterns and playful nuances, often presents us with linguistic puzzles that captivate our imagination. Anagrams, a fascinating linguistic phenomenon, delve into the art of rearranging letters to create new words or phrases with the same set of characters. Beyond the realm of language enthusiasts, anagrams pose a unique challenge in the world of computer science and programming.

In this blog post, we embark on a journey to explore an algorithmic solution to the Valid Anagram problem. The task at hand involves determining whether two strings are anagrams of each other, pushing us to unravel the complexities of string manipulation and algorithm design.

Overview

Anagrams, a linguistic puzzle where the letters of one word can be rearranged to form another, pose an interesting problem in computer science: how to determine if two strings are valid anagrams. In this blog post, we'll explore an algorithmic solution to this problem using Python. The provided function, isAnagram, efficiently checks whether two strings are anagrams of each other.

Code

Python

#Copyrights to venkys.io
#For more programs visit venkys.io 
#Python program for validAnagram
# Function to check if two strings are anagrams of each other
def isAnagram(string1, string2):
    # Check if the lengths of the strings are different; if so, they can't be anagrams
    if len(string1) != len(string2):
        return False
    
    # Dictionary to count the occurrences of each character in string1
    charcount = dict()
    
    # Count the occurrences of each character in string1
    for char in string1:
        if char in charcount.keys():
            charcount[char] += 1
        else:
            charcount[char] = 1
    
    # Compare the characters in string2 with the character count
    for char in string2:
        # If the character in string2 is not in the count dictionary or has reached 0 count, they're not anagrams
        if char not in charcount or charcount[char] == 0:
            return False
        else:
            charcount[char] -= 1  # Decrement the count of the character
    
    # Verify if both strings are anagrams by checking if all counts in the dictionary are 0
    for value in charcount.values():
        if value != 0:
            return False  # If any value is not 0, they're not anagrams
    
    return True  # Strings are anagrams

# take input string from the user
s= input()
t= input()
print(isAnagram(s, t))

Java

//Copyrights to venkys.io
//For more programs visit venkys.io 
//Java program for validAnagram
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class AnagramChecker {

    public static boolean isAnagram(String string1, String string2) {
        // Check if the lengths of the strings are different; if so, they can't be anagrams
        if (string1.length() != string2.length()) {
            return false;
        }

        // Map to count the occurrences of each character in string1
        Map<Character, Integer> charCount = new HashMap<>();

        // Count the occurrences of each character in string1
        for (char ch : string1.toCharArray()) {
            charCount.put(ch, charCount.getOrDefault(ch, 0) + 1);
        }

        // Compare the characters in string2 with the character count
        for (char ch : string2.toCharArray()) {
            // If the character in string2 is not in the count map or has reached 0 count, they're not anagrams
            if (!charCount.containsKey(ch) || charCount.get(ch) == 0) {
                return false;
            } else {
                charCount.put(ch, charCount.get(ch) - 1); // Decrement the count of the character
            }
        }

        // Verify if both strings are anagrams by checking if all counts in the map are 0
        for (int count : charCount.values()) {
            if (count != 0) {
                return false; // If any value is not 0, they're not anagrams
            }
        }

        return true; // Strings are anagrams
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        // Read the string input from the user
        String s = scanner.nextLine();
        String t = scanner.nextLine();

        // Close the scanner to prevent resource leaks
        scanner.close();
        System.out.println(isAnagram(s, t));
}

cpp

//Copyrights to venkys.io
//For more programs visit venkys.io 
//cpp program for validAnagram
#include <iostream>
#include <unordered_map>
using namespace std;

bool isAnagram(const std::string& string1, const std::string& string2) {
    // Check if the lengths of the strings are different; if so, they can't be anagrams
    if (string1.length() != string2.length()) {
        return false;
    }

    // Map to count the occurrences of each character in string1
    std::unordered_map<char, int> charCount;

    // Count the occurrences of each character in string1
    for (char ch : string1) {
        charCount[ch]++;
    }

    // Compare the characters in string2 with the character count
    for (char ch : string2) {
        // If the character in string2 is not in the count map or has reached 0 count, they're not anagrams
        if (charCount.find(ch) == charCount.end() || charCount[ch] == 0) {
            return false;
        } else {
            charCount[ch]--; // Decrement the count of the character
        }
    }

    // Verify if both strings are anagrams by checking if all counts in the map are 0
    for (const auto& pair : charCount) {
        if (pair.second != 0) {
            return false; // If any value is not 0, they're not anagrams
        }
    }

    return true; // Strings are anagrams
}

int main() {
    // Test the function with two strings
    std::string s;
    std::getline(std::cin, s);
    std::string t;
    std::getline(std::cin, t);
    cout << std::boolalpha << isAnagram(s, t) << std::endl; 

    return 0;
}

Step-by-Step Explanation

The provided code defines a function isAnagram that checks whether two input strings (string1 and string2) are anagrams of each other. An anagram is a word or phrase formed by rearranging the letters of another. The function starts by comparing the lengths of the two strings; if they are different, the function immediately returns False since strings of different lengths cannot be anagrams.

The function then creates a dictionary called charcount to store the count of each character in string1. It iterates through each character in string1, updating the count in the dictionary. After counting the characters in string1, the function compares the characters in string2 with the counts in the dictionary. If a character is not in the dictionary or its count becomes zero, the function returns False, indicating that the strings are not anagrams.

If the characters in both strings match and the counts are appropriately decremented, the function proceeds to a final check. It verifies that all counts in the dictionary are zero, ensuring that the characters in string2 are exactly the same as those in string1. If this condition is met, the function returns True, indicating that the input strings are anagrams; otherwise, it returns False.

The provided test case with strings "anagram" and "nagaram" demonstrates that the function correctly identifies them as anagrams, as the output is True.

Time and Space Complexity Analysis

To ensure the efficiency of the algorithm, let's delve into the time and space complexity of the code.

Time Complexity: O(n)

The time complexity is linear, where 'n' is the length of the strings. The loops iterate through each character in both strings, and the verification loop also iterates through the dictionary.

Space Complexity: O(1)

The space complexity is constant, as the dictionary's size is determined by the unique characters in the strings, not the length of the strings.

Real-World Applications

Understanding the Valid Anagram problem and its algorithmic solution has implications in various real-world scenarios. Let's explore some applications:

Cryptanalysis and Cryptography: Anagrams play a role in creating or breaking codes.
Data Validation: Ensuring data consistency and integrity in databases.
Word Games and Puzzles: Anagram-solving is central to games like Scrabble.
Plagiarism Detection: Identifying paraphrased content through anagram analysis.
String Comparison in Search Algorithms: Anagram-based techniques in search engines.
Biomedical Research: Comparing genetic sequences for mutation analysis.

This function, though seemingly simple, is a powerful tool in the broader landscape of problem-solving and algorithmic thinking. By exploring and understanding such code, programmers enhance their skills and gain valuable insights applicable across diverse domains.

Test Cases

Input:
"hello"
"world"
Output: False

Explanation: The lengths of s and t are different (5 and 5 respectively), so they cannot be anagrams. Therefore, the output is False.
Input:
"listen"
"silent"
Output: True

Explanation: Both s and t contain the same characters with the same frequencies. Therefore, they are anagrams of each other.

Copyrights to venkys.io

For more engaging programs and coding insights, visit venkys.io. The code provided here is a testament to the depth and versatility of programming challenges, and venkys.io offers a wealth of resources for those eager to delve deeper into the world of coding.