Valid Anagram

▶

Steps

setup

Check Lengths of s and t

The algorithm compares the lengths of s and t to quickly rule out non-anagrams if lengths differ.

💡 If lengths differ, no need to check characters; this saves time.

Line:

if len(s) != len(t):
    return False

💡 Length equality is a necessary condition for anagrams.

setup

Initialize Frequency Count Array

Create an array of size 26 initialized to zero to hold counts for each letter a-z.

💡 This array will track how many times each character appears in s and t.

Line:

count = [0] * 26

💡 Using a fixed-size array is efficient for lowercase English letters.

fill_row

Increment count for 'a' from s

Process first character 'a' in s, increment count at index for 'a' (0).

💡 Incrementing count means we found one occurrence of 'a' in s.

Line:

for ch in s:
    count[ord(ch) - ord('a')] += 1

💡 Each increment builds the frequency profile of s.

fill_row

Increment count for 'n' from s

Process second character 'n' in s, increment count at index for 'n' (13).

💡 Incrementing count for 'n' adds to s's frequency profile.

Line:

for ch in s:
    count[ord(ch) - ord('a')] += 1

💡 Frequency counts accumulate for each character in s.

fill_row

Increment count for 'a' from s again

Process third character 'a' in s, increment count for 'a' again (now 2).

💡 Multiple occurrences increase the count accordingly.

Line:

for ch in s:
    count[ord(ch) - ord('a')] += 1

💡 Counts reflect total frequency, not just presence.

fill_row

Decrement count for 'n' from t

Process first character 'n' in t, decrement count for 'n' (from 1 to 0).

💡 Decrementing count means matching character found in t, balancing frequency.

Line:

for ch in t:
    count[ord(ch) - ord('a')] -= 1

💡 Matching characters reduce the frequency difference.

fill_row

Decrement count for 'a' from t

Process second character 'a' in t, decrement count for 'a' (from 2 to 1).

💡 Each decrement balances the count for characters found in t.

Line:

for ch in t:
    count[ord(ch) - ord('a')] -= 1

💡 Partial balancing shows progress toward confirming anagram.

fill_row

Decrement count for 'g' from t

Process third character 'g' in t, decrement count for 'g' (from 0 to -1).

💡 If count goes negative, it means t has more of this character than s.

Line:

for ch in t:
    count[ord(ch) - ord('a')] -= 1
    if count[ord(ch) - ord('a')] < 0:
        return False

💡 Negative count would cause early return, but here it is first decrement for 'g' so count goes from 0 to -1 means 'g' was not incremented yet, so this is a mismatch.

fill_row

Increment count for 'g' from s

Process fourth character 'g' in s, increment count for 'g' (from -1 to 0).

💡 Incrementing 'g' balances the previous decrement, showing matching frequency.

Line:

for ch in s:
    count[ord(ch) - ord('a')] += 1

💡 Order of processing s and t characters affects intermediate counts but final balance matters.

fill_row

Decrement count for 'r' from t

Process fourth character 'r' in t, decrement count for 'r' (from 0 to -1).

💡 Decrementing 'r' shows t has one 'r' to balance with s.

Line:

for ch in t:
    count[ord(ch) - ord('a')] -= 1

💡 Intermediate negative counts may appear but will be balanced if anagram.

fill_row

Increment count for 'r' from s

Process fifth character 'r' in s, increment count for 'r' (from -1 to 0).

💡 Increment balances previous decrement, confirming matching frequency.

Line:

for ch in s:
    count[ord(ch) - ord('a')] += 1

💡 Balanced counts indicate matching characters in both strings.

fill_row

Decrement count for 'a' from t

Process fifth character 'a' in t, decrement count for 'a' (from 1 to 0).

💡 Decrementing 'a' balances the count, moving toward zero.

Line:

for ch in t:
    count[ord(ch) - ord('a')] -= 1

💡 Balanced counts for repeated characters confirm frequency match.

fill_row

Decrement count for 'm' from t

Process sixth character 'm' in t, decrement count for 'm' (from 0 to -1).

💡 Decrementing 'm' introduces a new character count to track.

Line:

for ch in t:
    count[ord(ch) - ord('a')] -= 1

💡 New characters appear as counts move from 0 to -1 before s increments them.

fill_row

Increment count for 'm' from s

Process sixth character 'm' in s, increment count for 'm' (from -1 to 0).

💡 Increment balances the count, confirming matching frequency.

Line:

for ch in s:
    count[ord(ch) - ord('a')] += 1

💡 Balanced counts for all characters processed so far.

fill_row

Decrement count for 'a' from t

Process seventh character 'a' in t, decrement count for 'a' (from 0 to -1).

💡 Decrementing 'a' again shows repeated character balancing.

Line:

for ch in t:
    count[ord(ch) - ord('a')] -= 1

💡 Repeated characters must be balanced exactly.

fill_row

Increment count for 'a' from s

Process seventh character 'a' in s, increment count for 'a' (from -1 to 0).

💡 Final increment balances the last character count.

Line:

for ch in s:
    count[ord(ch) - ord('a')] += 1

💡 All counts balanced to zero means strings are anagrams.

compare

Verify all counts are zero

Check if all counts in the array are zero, confirming s and t have identical character frequencies.

💡 If any count is not zero, strings are not anagrams.

Line:

return all(x == 0 for x in count)

💡 Balanced counts prove s and t are anagrams.

def isAnagram(s: str, t: str) -> bool:
    # STEP 1
    if len(s) != len(t):
        return False
    # STEP 2
    count = [0] * 26
    # STEP 3-5
    for ch in s:
        count[ord(ch) - ord('a')] += 1
    # STEP 6-16
    for ch in t:
        count[ord(ch) - ord('a')] -= 1
        if count[ord(ch) - ord('a')] < 0:
            return False
    # STEP 17
    return all(x == 0 for x in count)

if __name__ == '__main__':
    print(isAnagram('anagram', 'nagaram'))  # True
    print(isAnagram('rat', 'car'))          # False

📊

Valid Anagram - Watch the Algorithm Execute, Step by Step

Watching each character's count change helps you understand how frequency counting confirms if two strings are anagrams without sorting or complex data structures.

check

empty map

insert

empty map

increment

Lookup: a→ 0

a→1lookup

increment

Lookup: n→ 0

a→1

n→1lookup

increment

Lookup: a→ 1

a→2lookup

n→1

decrement

Lookup: n→ 1

a→2

n→0lookup

decrement

Lookup: a→ 2

a→1lookup

n→0

decrement

Lookup: g→ 0

a→1

n→0

g→-1lookup

increment

Lookup: g→ -1

a→1

n→0

g→0lookup

decrement

Lookup: r→ 0

a→1

n→0

g→0

r→-1lookup

increment

Lookup: r→ -1

a→1

n→0

g→0

r→0lookup

decrement

Lookup: a→ 1

a→0lookup

n→0

g→0

r→0

decrement

Lookup: m→ 0

a→0

n→0

g→0

r→0

m→-1lookup

increment

Lookup: m→ -1

a→0

n→0

g→0

r→0

m→0lookup

decrement

Lookup: a→ 0

a→-1lookup

n→0

g→0

r→0

m→0

increment

Lookup: a→ -1

a→0lookup

n→0

g→0

r→0

m→0

check

a→0

n→0

g→0

r→0

m→0

Result: true

Key Takeaways

✓ Frequency counting using a fixed-size array efficiently checks anagrams without sorting.

Code alone hides how counts increment and decrement; visualization reveals the balancing act clearly.

✓ Intermediate negative counts during decrement do not always mean failure; final balance matters.

Seeing counts go negative and then back to zero helps understand why early returns only happen if negative counts persist.

✓ Length check is a quick filter that avoids unnecessary computation.

This step is often overlooked but is critical for performance and correctness.

Practice

1. 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

2. What is the time complexity of the optimal Happy Number detection algorithm that uses a known set of unhappy cycle numbers and repeatedly computes the sum of squares of digits until termination?

medium

A. O(n) where n is the input number

B. O(k * n) where k is iterations and n is the number of digits

C. O(log n) because each iteration reduces the number size drastically

D. O(k * log n) where k is the number of iterations until 1 or cycle

Solution

1. Step 1: Identify cost per iteration

   Each iteration computes sum of squares of digits, which takes O(log n) time since number of digits is proportional to log n.

2. Step 2: Count iterations until termination

   There are k iterations until number reaches 1 or cycle; total time is O(k * log n).

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Time depends on iterations and digit count, not linear in n [OK]

Hint: Sum of squares per iteration costs O(log n) [OK]

Common Mistakes:

• Confusing input size n with number of digits
• Assuming linear O(n) time

3. What is the time complexity of the optimal hash set approach for finding the longest consecutive sequence in an array of size n?

medium

A. O(n log n) due to sorting inside the algorithm

B. O(n) because each number is processed at most twice

C. O(n²) because of nested loops checking consecutive numbers

D. O(n) average but O(n²) worst case due to hash collisions

Solution

1. Step 1: Analyze outer loop

   The outer loop iterates over each unique number once.

2. Step 2: Analyze inner while loop

   Each number is visited at most once in the inner loop when counting consecutive sequences, so total work is O(n).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Hash set lookups are O(1), total linear time [OK]

Hint: Each element visited once in sequence counting [OK]

Common Mistakes:

• Assuming sorting is involved causing O(n log n)
• Confusing nested loops as O(n²)
• Overestimating hash collision impact

4. Suppose the problem is modified so that characters can be reused multiple times and you want to find the first unique character index after removing all duplicates. Which modification to the optimal approach correctly handles this variant?

hard

A. Sort the string and pick the first character that appears once, ignoring original indices.

B. Use a queue to track characters as they appear and remove duplicates dynamically during iteration.

C. Use the same frequency map approach but only consider characters with frequency exactly one after removal.

D. Use a brute force nested loop to check uniqueness after each removal.

Solution

1. Step 1: Understand the reuse and removal requirement

   Characters can be reused, so duplicates must be removed dynamically to find first unique.

2. Step 2: Identify approach that dynamically tracks uniqueness

   A queue can track order and remove duplicates as they appear, maintaining first unique efficiently.

3. Step 3: Evaluate other options

   Sorting loses original order; brute force is inefficient; frequency map alone can't handle dynamic removals.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Queue-based approach handles dynamic uniqueness correctly [OK]

Hint: Dynamic uniqueness needs a queue, not just frequency map [OK]

Common Mistakes:

• Assuming static frequency map suffices
• Sorting loses original order
• Brute force is too slow

5. Suppose the problem is modified so that negative integers are allowed as input. Which of the following changes to the optimal Happy Number detection algorithm correctly handles negative inputs without breaking correctness or efficiency?

hard

A. Reject negative inputs immediately as invalid and return false

B. Add negative numbers to the unhappy cycle set to detect cycles quickly

C. Ignore the sign and compute sum of squares of digits of the absolute value; proceed as usual

D. Modify sum_of_squares to include the sign squared (which is always positive) and proceed

Solution

1. Step 1: Consider negative input handling

   Sum of squares of digits depends on digits, not sign; absolute value preserves digits.

2. Step 2: Verify correctness and efficiency

   Using absolute value avoids complexity and maintains correctness; no need to add negatives to cycle set or reject.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Absolute value preserves digit sums and cycle detection [OK]

Hint: Use absolute value to handle negative inputs [OK]

Common Mistakes:

• Adding negatives to cycle set
• Rejecting negatives unnecessarily