Intuition

The letters of an anagram should form identically sequences if alphabetically sorted. By furthering this thought process a method to check for anagrams would be sorting both strings. By sorting both strings and then comparing them, we can easily determine if they contain the same characters in the same frequencies.

Approach

Sort the characters of both strings using an inbuilt sort function, so that if they are anagrams, the sorted strings will be identical.
Compare the sorted versions of both strings. If they match, the original strings are anagrams; otherwise, they are not.
Return true if the sorted strings are identical, otherwise return false.

Dry Run

Solution

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    bool anagramStrings(string& s, string t) {
        // If lengths are not equal, they cannot be anagrams
        if (s.length() != t.length()) return false;

        // Sort both strings
        sort(s.begin(), s.end());
        sort(t.begin(), t.end());

        // Compare sorted strings
        return s == t;
    }
};

int main() {
    Solution solution;
    string str1 = "INTEGER";
    string str2 = "TEGERNI";
    bool result = solution.anagramStrings(str1, str2);
    cout << (result ? "True" : "False") << endl;
    return 0;
}

import java.util.Arrays;

class Solution {
    public boolean anagramStrings(String s, String t) {
        // If lengths are not equal, they cannot be anagrams
        if (s.length() != t.length()) return false;

        // Convert strings to char arrays and sort them
        char[] sArray = s.toCharArray();
        char[] tArray = t.toCharArray();
        Arrays.sort(sArray);
        Arrays.sort(tArray);

        // Compare sorted arrays
        return Arrays.equals(sArray, tArray);
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        String str1 = "INTEGER";
        String str2 = "TEGERNI";
        boolean result = solution.anagramStrings(str1, str2);
        System.out.println(result ? "True" : "False");
    }
}
class Solution:
    def anagramStrings(self, s, t):
        # If lengths are not equal, they cannot be anagrams
        if len(s) != len(t):
            return False
        
        # Sort both strings and compare
        return sorted(s) == sorted(t)

if __name__ == "__main__":
    solution = Solution()
    str1 = "INTEGER"
    str2 = "TEGERNI"
    result = solution.anagramStrings(str1, str2)
    print("True" if result else "False")
class Solution {
    anagramStrings(s, t) {
        // If lengths are not equal, they cannot be anagrams
        if (s.length !== t.length) return false;

        // Sort both strings and compare
        return s.split('').sort().join('') === t.split('').sort().join('');
    }
}

const solution = new Solution();
const str1 = "INTEGER";
const str2 = "TEGERNI";
const result = solution.anagramStrings(str1, str2);
console.log(result ? "True" : "False");

Complexity Analysis

Time Complexity: O(N log N) due to sorting each string.

Space Complexity: O(1) as no additional data structures are used. Note that for Java, the space complexity will be O(N) due to the creation of additional character arrays.

Intuition:

An alternative approach to checking anagrams is to check the number of times each character in both strings appears through frequency counting. The frequency counting method for checking if two strings are anagrams is based on the idea that two strings are anagrams if they have the same characters appearing the same number of times. By counting the frequency of each character in the first string and then decreasing the count for each character in the second string, we can ensure that both strings have identical character distributions. If any character count does not return to zero, the strings are not anagrams.

Approach:

Initialize a frequency array of size 26 to count the occurrences of each letter in the first string (Str1). Each index of the array represents a letter from 'a' to 'z'.
Iterate through the second string (Str2) and decrease the count in the frequency array for each letter found in Str2. This ensures we are balancing out the counts from Str1.
Check the frequency array. If all counts return to zero, both strings have identical character frequencies and are anagrams. If any count is not zero, the strings are not anagrams.

Dry Run:

Solution:

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    bool anagramStrings(string &s, string &t) {
        // Edge Cases
        if (s.length() != t.length()) return false;

        // To store the count of each character
        vector<int> count(26, 0);

        // Count occurence of each character in first string 
        for (char c : s) count[c - 'a']++;

        // Decrement the count for each character in the second string
        for (char c : t) count[c - 'a']--;

        // Check for count of every character
        for (int i : count) {
            // If the count is not zero
            if (i != 0) return false; // Return false
        }

        // Otherwise strings are anagram
        return true;
    }
};

int main() {
    string str1 = "integer";
    string str2 = "tegerni";
    
    // Creating an instance of Solution class
    Solution sol;
    
    /* Function call to find out 
    whether two strings are anagram */
    bool result = sol.anagramStrings(str1, str2);
    
    // Output 
    if(result) cout << "The given strings are anagrams.";
    else cout << "The given strings are not anagrams.";
    
    return 0;
}
import java.util.*;

class Solution {
    public boolean anagramStrings(String s, String t) {
        // Edge Cases
        if (s.length() != t.length()) return false;

        // To store the count of each character
        int[] count = new int[26];

        // Count occurrence of each character in first string 
        for (char c : s.toCharArray()) count[c - 'a']++;

        // Decrement the count for each character in the second string
        for (char c : t.toCharArray()) count[c - 'a']--;

        // Check for count of every character
        for (int i : count) {
            // If the count is not zero
            if (i != 0) return false; // Return false
        }

        // Otherwise strings are anagram
        return true;
    }
}

class Main {
    public static void main(String[] args) {
        String str1 = "integer";
        String str2 = "tegerni";

        // Creating an instance of Solution class
        Solution sol = new Solution();

        /* Function call to find out 
        whether two strings are anagram */
        boolean result = sol.anagramStrings(str1, str2);

        // Output 
        if (result) System.out.println("The given strings are anagrams.");
        else System.out.println("The given strings are not anagrams.");
    }
}
class Solution:
    def anagramStrings(self, s, t):
        # Edge Cases
        if len(s) != len(t):
            return False

        # To store the count of each character
        count = [0] * 26

        # Count occurrence of each character in first string 
        for c in s:
            count[ord(c) - ord('a')] += 1

        # Decrement the count for each character in the second string
        for c in t:
            count[ord(c) - ord('a')] -= 1

        # Check for count of every character
        for i in count:
            # If the count is not zero
            if i != 0:
                return False # Return false

        # Otherwise strings are anagram
        return True

if __name__ == "__main__":
    str1 = "integer"
    str2 = "tegerni"

    # Creating an instance of Solution class
    sol = Solution()

    '''Function call to find out 
    whether two strings are anagram'''
    result = sol.anagramStrings(str1, str2)

    # Output 
    if result:
        print("The given strings are anagrams.")
    else:
        print("The given strings are not anagrams.")
class Solution {
    anagramStrings(s, t) {
        // Edge Cases
        if (s.length !== t.length) return false;

        // To store the count of each character
        let count = new Array(26).fill(0);

        // Count occurrence of each character in first string 
        for (let c of s) count[c.charCodeAt(0) - 'a'.charCodeAt(0)]++;

        // Decrement the count for each character in the second string
        for (let c of t) count[c.charCodeAt(0) - 'a'.charCodeAt(0)]--;

        // Check for count of every character
        for (let i of count) {
            // If the count is not zero
            if (i !== 0) return false; // Return false
        }

        // Otherwise strings are anagram
        return true;
    }
}

const str1 = "integer";
const str2 = "tegerni";

// Creating an instance of Solution class
const sol = new Solution();

/* Function call to find out 
whether two strings are anagram */
const result = sol.anagramStrings(str1, str2);

// Output 
if(result) console.log("The given strings are anagrams.");
else console.log("The given strings are not anagrams.");

Complexity Analysis:

Time Complexity: O(N), where N is the length of the string

Space Complexity: O(1) as no additional data structures are used

Problem List

Valid Anagram

Examples:

Constraints

Company Tags

Editorial