Valid Anagram

📋

Problem

Imagine you want to quickly check if two words are just jumbled versions of each other, like 'listen' and 'silent'. This problem helps you verify that efficiently.

Given two strings s and t, write a function to determine if t is an anagram of s. 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 a different word or phrase, using all the original letters exactly once.

1 ≤ length of s, t ≤ 10^5s and t consist of lowercase English letters only

Edge cases: Empty strings s = '', t = '' → trueStrings of different lengths s = 'a', t = 'aa' → falseStrings with same letters but different counts s = 'aabb', t = 'abab' → true

</>

IDE

def isAnagram(s: str, t: str) -> bool:public boolean isAnagram(String s, String t)bool isAnagram(string s, string t)function isAnagram(s, t)

def isAnagram(s: str, t: str) -> bool:
    # Write your solution here
    pass

class Solution {
    public boolean isAnagram(String s, String t) {
        // Write your solution here
        return false;
    }
}

#include <string>
using namespace std;

bool isAnagram(string s, string t) {
    // Write your solution here
    return false;
}

function isAnagram(s, t) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: trueNot checking length equality before frequency counting, causing false positives.✅ Add a length check: if len(s) != len(t): return False

Wrong: falseComparing strings directly or sorting incorrectly, failing to recognize anagrams with same counts.✅ Use frequency counting or correct sorting comparison: return sorted(s) == sorted(t)

Wrong: falseOrder sensitivity bug: comparing strings directly without sorting or counting.✅ Use frequency counts or sort both strings before comparing.

Wrong: truePartial frequency counting or ignoring extra characters in one string.✅ Count all characters and verify counts match exactly; check length equality.

Wrong: timeoutUsing sorting or nested loops on large inputs causing TLE.✅ Implement O(n) frequency counting using fixed-size array for lowercase letters.

✓

Test Cases

Try testing your code with empty strings and strings of different lengths.

Consider tricky cases where order differs but counts match, or lengths differ subtly.

Optimize your solution to linear time using fixed-size frequency arrays.

t1_01basic

Input{"s":"anagram","t":"nagaram"}

Expectedtrue

⏱ Performance - must finish in 2000ms

Both strings have the same characters with the same frequency.

💡 Check if both strings have the same length first.

💡 Count the frequency of each character in both strings and compare.

💡 Use a hash map or array to count characters and verify counts match exactly.

Why it failed: Failed to verify character frequencies correctly or skipped length check. Fix by ensuring length equality and frequency counts match exactly.

✓ Correctly identified strings as anagrams by matching character counts.

t1_02basic

Input{"s":"rat","t":"car"}

Expectedfalse

⏱ Performance - must finish in 2000ms

Strings have different characters; 'rat' and 'car' are not anagrams.

💡 Check if lengths differ; if yes, return false immediately.

💡 Compare character counts to detect mismatches.

💡 Return false as soon as a character count mismatch is found.

Why it failed: Incorrectly returned true despite different character sets. Fix by verifying character counts and returning false on mismatch.

✓ Correctly identified strings as not anagrams due to differing character counts.

t2_01edge

Input{"s":"","t":""}

Expectedtrue

⏱ Performance - must finish in 2000ms

Empty strings are trivially anagrams of each other.

💡 Consider the case when both strings are empty.

💡 Empty strings have zero length and zero character counts.

💡 Return true if both strings are empty.

Why it failed: Failed to handle empty strings correctly; possibly returning false or error. Fix by returning true when both strings are empty.

✓ Correctly handled empty strings as anagrams.

t2_02edge

Input{"s":"a","t":"aa"}

Expectedfalse

⏱ Performance - must finish in 2000ms

Strings have different lengths; cannot be anagrams.

💡 Check length equality before counting characters.

💡 If lengths differ, return false immediately.

💡 Avoid unnecessary counting if lengths differ.

Why it failed: Did not check length equality first, leading to incorrect true result. Fix by adding length check before frequency counting.

✓ Correctly returned false for strings of different lengths.

t2_03edge

Input{"s":"aabb","t":"abab"}

Expectedtrue

⏱ Performance - must finish in 2000ms

Both strings have the same characters with the same frequency, just different order.

💡 Order of characters does not matter for anagrams.

💡 Count frequency of each character and compare counts.

💡 Return true if all character counts match.

Why it failed: Incorrectly failed due to order sensitivity. Fix by comparing frequency counts instead of string order.

✓ Correctly identified anagrams despite different character order.

t3_01corner

Input{"s":"aabbcc","t":"abcabc"}

Expectedtrue

⏱ Performance - must finish in 2000ms

Strings have same character counts but different grouping; tests order independence.

💡 Anagrams depend on character counts, not order.

💡 Use frequency counting, not sorting only.

💡 Ensure frequency counts match exactly for all characters.

Why it failed: Failed due to incorrect sorting or partial frequency counting. Fix by counting all characters fully and comparing counts.

✓ Correctly handled character count matching regardless of grouping.

t3_02corner

Input{"s":"aabbcc","t":"aabbc"}

Expectedfalse

⏱ Performance - must finish in 2000ms

Strings differ in length by one; tests length check and frequency mismatch.

💡 Check length equality first.

💡 If lengths differ, return false immediately.

💡 Avoid counting if lengths differ.

Why it failed: Missed length check causing incorrect true result. Fix by adding length equality check before frequency counting.

✓ Correctly returned false for strings with different lengths.

t3_03corner

Input{"s":"abc","t":"abcc"}

Expectedfalse

⏱ Performance - must finish in 2000ms

Tests handling of extra characters in one string; not anagrams.

💡 Length check is crucial to catch this case.

💡 Frequency counts must match exactly.

💡 Return false if any character count differs.

Why it failed: Failed to detect extra character causing false positive. Fix by verifying exact frequency match and length equality.

✓ Correctly identified strings as not anagrams due to extra character.

t4_01performance

Input{"_description":"n=100000 at constraint boundary - executor generates this"}

Expectednull

⏱ Performance - must finish in 2000ms

Input size n=100000 requires O(n) solution to complete within 2 seconds.

💡 Sorting O(n log n) might be borderline; frequency counting O(n) is optimal.

💡 Use fixed-size array for character counts since input is lowercase letters only.

💡 Avoid nested loops or repeated scans to meet time constraints.

Why it failed: TLE due to using O(n log n) or worse approach. Fix by implementing O(n) frequency counting with fixed-size array.

✓ Solution runs in O(n) time and passes performance constraints.

Practice

1. You need to design a data structure that supports inserting elements, deleting elements, and retrieving a random element, all in average constant time. Which approach best guarantees this performance?

easy

A. Using a balanced binary search tree to maintain elements and their indices

B. Combining a hash map for element indices with an array to store elements, using a swap-delete trick on removal

C. Using a linked list for elements and a hash set for membership checks

D. Maintaining a sorted array and performing binary search for insertions and deletions

Solution

1. Step 1: Understand operation requirements

   Insert, delete, and getRandom must all be O(1) average time.

2. Step 2: Evaluate data structures

   Balanced BST or sorted array have O(log n) or worse for insert/delete. Linked list lacks O(1) random access. Hash map + array with swap-delete achieves O(1) for all operations.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Hash map + array with swap-delete is the classic O(1) solution [OK]

Hint: Hash map + array with swap-delete enables O(1) ops [OK]

Common Mistakes:

• Thinking balanced BST gives O(1) insert/delete
• Using linked list for O(1) random access
• Assuming sorted array can do O(1) insert/delete

2. Consider the following Python code implementing the optimal approach for finding the intersection of two arrays. What is the final returned list when calling intersect([4,9,5], [9,4,9,8,4])?

def intersect(nums1, nums2):
    nums1.sort()
    nums2.sort()
    i, j = 0, 0
    intersection = []
    while i < len(nums1) and j < len(nums2):
        if nums1[i] == nums2[j]:
            intersection.append(nums1[i])
            i += 1
            j += 1
        elif nums1[i] < nums2[j]:
            i += 1
        else:
            j += 1
    return intersection

easy

A. [4, 4, 9]

B. [9, 9]

C. [4, 9]

D. [4, 9, 5]

Solution

1. Step 1: Sort both arrays

   nums1 sorted: [4,5,9], nums2 sorted: [4,4,8,9,9]

2. Step 2: Traverse with two pointers

   Compare 4 and 4 -> equal, add 4; i=1, j=1 Compare 5 and 4 -> 5>4, increment j=2 Compare 5 and 8 -> 5<8, increment i=2 Compare 9 and 8 -> 9>8, increment j=3 Compare 9 and 9 -> equal, add 9; i=3, j=4 (end)

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Intersection is [4,9] matching common elements with duplicates counted correctly [OK]

Hint: Sort arrays and advance pointers carefully [OK]

Common Mistakes:

• Off-by-one errors in pointer increments
• Including extra duplicates
• Returning unsorted results

3. What is the average time complexity of the remove operation in the optimal Insert Delete GetRandom data structure that uses a hash map and an array with the swap-delete trick?

medium

A. O(n), because removing an element requires shifting elements in the array

B. O(log n), because hash map operations take logarithmic time on average

C. O(1), because swapping with the last element and updating the hash map takes constant time

D. O(1) amortized, but worst-case O(n) due to occasional resizing of the array

Solution

1. Step 1: Identify operations in remove

   Remove finds index in O(1) via hash map, swaps with last element, updates hash map, and pops last element.

2. Step 2: Analyze time per step

   All steps are O(1) average time; no shifting of elements occurs.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Swap-delete avoids O(n) shifting, ensuring O(1) remove [OK]

Hint: Swap-delete avoids shifting, so remove is O(1) [OK]

Common Mistakes:

• Assuming array remove requires shifting O(n)
• Confusing hash map average O(1) with O(log n)
• Ignoring that resizing is amortized and rare

4. What is the time complexity of the optimal sorting + two pointers approach for finding the intersection of two arrays of sizes m and n, respectively?

medium

A. O(m * n)

B. O(m log m + n log n)

C. O(m + n)

D. O(min(m, n) * log(max(m, n)))

Solution

1. Step 1: Identify sorting cost

   Sorting nums1 costs O(m log m), sorting nums2 costs O(n log n).

2. Step 2: Identify two-pointer traversal cost

   Two-pointer traversal is O(m + n) which is dominated by sorting.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Sorting dominates, so total is O(m log m + n log n) [OK]

Hint: Sorting dominates time complexity [OK]

Common Mistakes:

• Confusing traversal cost as total
• Assuming nested loops complexity
• Misreading min/max in complexity

5. What is the time and space complexity of the optimal solution using prefix sums and a hash map (or array) for the longest subarray with sum divisible by k problem, given an input array of length n and integer k?

medium

A. Time: O(n log n), Space: O(n)

B. Time: O(n), Space: O(k)

C. Time: O(n * k), Space: O(n)

D. Time: O(n^2), Space: O(1)

Solution

1. Step 1: Analyze time complexity

   The algorithm iterates once over the array (length n), performing O(1) operations per element, so time is O(n).

2. Step 2: Analyze space complexity

   We store earliest indices for each remainder modulo k, so space is O(k), independent of n.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Linear time and space proportional to k [OK]

Hint: Prefix sums + hash map -> O(n) time, O(k) space [OK]

Common Mistakes:

• Confusing nested loops complexity with prefix sum approach
• Assuming space is O(n) due to prefix sums stored
• Thinking time is O(n*k) due to modulo operations