The Valid Anagram problem is a common interview question that checks whether two strings are anagrams of each other. Two strings are considered anagrams if they have the same characters with the same frequencies but may appear in a different order. For example, the strings "listen" and "silent" are anagrams.

In this post, we will explore multiple approaches to solve the Valid Anagram problem in C++. We'll go over different methods, discuss their time and space complexity, and address various edge cases.

Problem Definition

Given two strings s and t, write a function isAnagram that determines whether t is an anagram of s.

Example:

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

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

Constraints:

  • Both s and t consist of lowercase English letters.
  • The length of both strings can be up to (10^5).

Approach 1: Sorting-Based Solution

Explanation:

A simple way to determine if two strings are anagrams is to sort both strings and compare them. If the sorted strings are identical, they are anagrams; otherwise, they are not.

Code Implementation:

#include <iostream>
#include <algorithm>
#include <string>

bool isAnagram(std::string s, std::string t) {
    // If the lengths are different, they can't be anagrams
    if (s.length() != t.length()) {
        return false;
    }
    
    // Sort both strings and compare
    std::sort(s.begin(), s.end());
    std::sort(t.begin(), t.end());
    
    return s == t;
}

int main() {
    std::cout << isAnagram("anagram", "nagaram") << std::endl;  // Output: 1 (true)
    std::cout << isAnagram("rat", "car") << std::endl;  // Output: 0 (false)
}

Time and Space Complexity:

  • Time Complexity: O(n log n), where n is the length of the strings due to sorting.
  • Space Complexity: O(1) if we modify the strings in place (other than the input storage).

Explanation:

We first check if the strings have the same length (a necessary condition for them to be anagrams). Then, we sort both strings and compare them. If the sorted strings are identical, they are anagrams. This approach works but is not the most optimal due to the O(n log n) time complexity of sorting.

Approach 2: Frequency Count Using Hash Maps (Optimal Solution)

Explanation:

A more efficient way to solve the problem is to count the frequency of each character in both strings and compare these frequencies. We can use an array (or hash map) to store the frequency count for each character. If the frequencies match, the strings are anagrams.

Code Implementation:

#include <iostream>
#include <vector>
#include <string>

bool isAnagram(std::string s, std::string t) {
    // If the lengths are different, they can't be anagrams
    if (s.length() != t.length()) {
        return false;
    }
    
    // Create frequency arrays for both strings
    std::vector<int> char_count(26, 0);  // We use an array for 26 lowercase letters

    // Count characters in both strings
    for (int i = 0; i < s.length(); i++) {
        char_count[s[i] - 'a']++;  // Increment count for s
        char_count[t[i] - 'a']--;  // Decrement count for t
    }

    // Check if all counts are zero
    for (int count : char_count) {
        if (count != 0) {
            return false;
        }
    }

    return true;
}

int main() {
    std::cout << isAnagram("anagram", "nagaram") << std::endl;  // Output: 1 (true)
    std::cout << isAnagram("rat", "car") << std::endl;  // Output: 0 (false)
}

Time and Space Complexity:

  • Time Complexity: O(n), where n is the length of the strings. We loop through the strings once.
  • Space Complexity: O(1), since we use a fixed-size array (26 elements) to store the character frequencies.

Explanation:

We use a single frequency array of size 26 (for lowercase English letters). We increment the count for each character in s and decrement the count for each character in t. If the counts in the array are all zero after processing both strings, they are anagrams.

This approach is optimal in terms of both time and space complexity.

Edge Cases

When solving the Valid Anagram problem, it's important to account for various edge cases:

  1. Different Length Strings:
    If two strings have different lengths, they cannot be anagrams, so we can return false early.

    std::string s = "abcd";
std::string t = "abc";
std::cout << isAnagram(s, t) << std::endl;  // Output: 0 (false)

  2. Empty Strings:
    Two empty strings are considered anagrams since they contain the same characters (zero characters).

    std::string s = "";
std::string t = "";
std::cout << isAnagram(s, t) << std::endl;  // Output: 1 (true)

  3. Single Character Strings:
    Strings with one character can only be anagrams if they are identical.

    std::string s = "a";
std::string t = "a";
std::cout << isAnagram(s, t) << std::endl;  // Output: 1 (true)

std::string s = "a";
std::string t = "b";
std::cout << isAnagram(s, t) << std::endl;  // Output: 0 (false)

  4. Case Sensitivity:
    The problem assumes that all characters are lowercase, but if case sensitivity is a factor, "A" and "a" should not be considered the same. This must be addressed explicitly if the problem extends to case-sensitive inputs.

    std::string s = "a";
std::string t = "A";
std::cout << isAnagram(s, t) << std::endl;  // Output: 0 (false)

  5. Non-Alphabetic Characters:
    If the input strings contain non-alphabetic characters (e.g., punctuation or spaces), those characters should also be handled.

    std::string s = "a.b";
std::string t = "b.a";
std::cout << isAnagram(s, t) << std::endl;  // Output: 1 (true)

Conclusion

In this post, we explored different approaches to solving the Valid Anagram problem in C++. The sorting-based solution is simple but has a higher time complexity of O(n log n). The optimal solution uses a frequency count with an array, achieving O(n) time complexity and O(1) space complexity. By handling edge cases properly, you can ensure that your solution works efficiently in all scenarios.