NUHMAN.com

🔍 Problem Statement

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 another, such as "anagram" and "nagaram".

🧠 Approach

To check if two strings s and t are anagrams of each other:

1. Same Length: First, check if the two strings have the same length. If they don't, they cannot be anagrams.
2. Character Frequency Count: Then, count the frequency of characters in both strings. If the frequency of each character in both strings is the same, they are anagrams.
3. Sorting: Alternatively, you could sort both strings and compare if they are equal.

We'll implement the character frequency count approach, which is optimal with O(n) time complexity.

Steps:

1. Check the length: If the lengths of s and t are different, return false immediately.
2. Count frequencies: Use a hash map or array to count the frequency of each character in both strings.
3. Compare frequencies: If the frequency maps of both strings are identical, return true, otherwise false.

✅ Go Implementation

go

package main

import (
	"fmt"
)

// Function to check if two strings are anagrams
func isAnagram(s string, t string) bool {
	// If the lengths are not equal, they can't be anagrams
	if len(s) != len(t) {
		return false
	}

	// Create an array to count the frequency of characters
	charCount := make([]int, 26)

	// Count characters in the first string
	for i := 0; i < len(s); i++ {
		charCount[s[i]-'a']++
	}

	// Subtract counts based on characters in the second string
	for i := 0; i < len(t); i++ {
		charCount[t[i]-'a']--
		// If a character count goes negative, the strings are not anagrams
		if charCount[t[i]-'a'] < 0 {
			return false
		}
	}

	// If all counts are zero, the strings are anagrams
	return true
}

// Test the isAnagram function
func main() {
	// Example 1: "anagram" and "nagaram"
	s1, t1 := "anagram", "nagaram"
	fmt.Println(isAnagram(s1, t1)) // Output: true

	// Example 2: "rat" and "car"
	s2, t2 := "rat", "car"
	fmt.Println(isAnagram(s2, t2)) // Output: false
}

🧑‍💻 Explanation of the Code

1. isAnagram function:

• Step 1: First, we check if the lengths of s and t are equal. If they are not, we immediately return false because they cannot be anagrams.
• Step 2: We create an array charCount of size 26 (for the 26 lowercase English letters). This will be used to store the count of each character.
• Step 3: We iterate through the first string s and increase the count of each character in charCount.
• Step 4: We iterate through the second string t, and for each character, we decrease the corresponding count in charCount.
• Step 5: If, during the second loop, any count goes negative (i.e., charCount[t[i]-'a'] < 0), it means t contains a character more than s, so we return false.
• Step 6: If all counts are zero after processing both strings, return true as the strings are anagrams.

1. main function:

• We run the isAnagram function on two examples, "anagram" and "nagaram", and "rat" and "car", and print the results.

📦 Example Usage

go

func main() {
	// Example 1: "anagram" and "nagaram"
	s1, t1 := "anagram", "nagaram"
	fmt.Println(isAnagram(s1, t1)) // Output: true

	// Example 2: "rat" and "car"
	s2, t2 := "rat", "car"
	fmt.Println(isAnagram(s2, t2)) // Output: false
}

Example Output:

arduino

true
false

⏱️ Time & Space Complexity

• Time Complexity: The time complexity is O(n), where n is the length of the strings. We iterate through both strings once to count the characters.
• Space Complexity: The space complexity is O(1), since the array charCount is always of fixed size (26 for lowercase English letters), regardless of the input size.

This solution efficiently solves the problem with linear time complexity.