algoadvance

Leetcode 242. Valid Anagram Sure! Let’s go through the problem-solving process for “242. Valid Anagram” from LeetCode.

Problem Statement

Given two strings s and t, write a function to determine if t is an anagram of s.

Example 1:

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

Example 2:

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

Note:

Clarifying Questions

  1. Input Constraints: Are the input strings limited to a specific length?
  2. Case Sensitivity: Are the comparisons case-sensitive? However, for this problem, it’s stated that the strings contain only lowercase alphabets.
  3. Space Complexity Considerations: Can we use extra space for counting characters?

Assuming we have clarity and no further questions, we can move on to the strategy.

Strategy

An anagram requires that both strings, when sorted, look the same. Thus, the character counts should match for both strings.

There are two primary ways to solve this problem:

  1. Sorting Method:
    • Sort both strings.
    • Compare the sorted strings.
  2. Frequency Counting Method:
    • Use a dictionary or an array (since only lowercase alphabets) to count the frequency of each character in both strings.
    • Compare the frequency counts.

We will use the Frequency Counting Method as it generally offers better performance.

Time Complexity

The Sorting Method would involve O(n log n) time complexity due to sorting. The Frequency Counting Method operates in O(n) time for counting and comparing, where n is the length of the strings.

Code

Here is the solution using the Frequency Counting Method:

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

bool isAnagram(std::string s, std::string t) {
    if (s.size() != t.size()) {
        return false;
    }

    std::vector<int> count(26, 0); // Since there are 26 lowercase letters

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

    for (int i = 0; i < 26; ++i) {
        if (count[i] != 0) {
            return false;
        }
    }

    return true;
}

int main() {
    std::string s = "anagram";
    std::string t = "nagaram";
    
    if (isAnagram(s, t)) {
        std::cout << "The strings are anagrams." << std::endl;
    } else {
        std::cout << "The strings are not anagrams." << std::endl;
    }

    return 0;
}

Explanation

  1. Vector Initialization: We initialize a vector count of size 26 (for each letter of the alphabet) to keep track of character frequencies.
  2. Counting Frequencies: We simultaneously traverse both strings, incrementing the count for characters in s and decrementing for characters in t.
  3. Verification: After processing both strings, we check if all counts are zero. If any count is non-zero, it means the strings have different character frequencies, and thus, they are not anagrams.

By following this approach, we ensure an efficient O(n) time complexity solution.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI