Anagram Check Techniques in DSA Typescript - Execution Trace

Concept Flow - Anagram Check Techniques

Input two strings

↓

Choose technique

↓

Sort both

↓

Compare

↓

Result: True/False

Start with two strings, pick a method: sort and compare or count characters and compare counts, then decide if they are anagrams.

Execution Sample

DSA Typescript

function areAnagrams(s1: string, s2: string): boolean {
  if (s1.length !== s2.length) return false;
  const count: Record<string, number> = {};
  for (const char of s1) count[char] = (count[char] || 0) + 1;
  for (const char of s2) {
    if (!count[char]) return false;
    count[char]--;
  }
  return true;
}

Checks if two strings are anagrams by counting characters in the first and subtracting counts using the second.

Execution Table

Step	Operation	Character Processed	Count Map State	Action	Result
1	Check length	-	-	Lengths equal (4 == 4)	Continue
2	Count chars in s1	a	{"a":1}	Add 'a' count	-
3	Count chars in s1	r	{"a":1,"r":1}	Add 'r' count	-
4	Count chars in s1	t	{"a":1,"r":1,"t":1}	Add 't' count	-
5	Count chars in s1	s	{"a":1,"r":1,"t":1,"s":1}	Add 's' count	-
6	Subtract chars in s2	t	{"a":1,"r":1,"t":0,"s":1}	Subtract 't' count	-
7	Subtract chars in s2	a	{"a":0,"r":1,"t":0,"s":1}	Subtract 'a' count	-
8	Subtract chars in s2	r	{"a":0,"r":0,"t":0,"s":1}	Subtract 'r' count	-
9	Subtract chars in s2	s	{"a":0,"r":0,"t":0,"s":0}	Subtract 's' count	-
10	Check counts	-	{"a":0,"r":0,"t":0,"s":0}	All zero counts	Return true

💡 All character counts matched, strings are anagrams

Variable Tracker

Variable	Start	After Step 2	After Step 5	After Step 9	Final
count	{}	{"a":1}	{"a":1,"r":1,"t":1,"s":1}	{"a":0,"r":0,"t":0,"s":0}	{"a":0,"r":0,"t":0,"s":0}
s1.length	4	4	4	4	4
s2.length	4	4	4	4	4

Key Moments - 3 Insights

Why do we check if string lengths are equal before counting characters?

Because if lengths differ, they cannot be anagrams. This is shown in Step 1 of execution_table where unequal lengths would stop the process early.

Why do we subtract counts for characters in the second string?

Subtracting counts ensures each character in the second string matches the first. If any count goes below zero, it means extra characters exist, shown in Steps 6-9.

What if a character in the second string is not in the count map?

The code returns false immediately, as seen in Step 7 where if count[char] is zero or undefined, it means the strings differ.

Visual Quiz - 3 Questions

Look at the execution_table, what is the count map state after processing character 'r' in s1?

A {"a":1,"r":1}

B {"a":1,"r":1,"t":1}

C {"a":1,"r":1,"t":1,"s":1}

D {"r":1}

💡 Hint

Check Step 3 in execution_table for count map after 'r' is processed

At which step does the count for character 't' become zero?

A Step 8

B Step 5

C Step 6

D Step 9

💡 Hint

Look at Step 6 in execution_table where 't' count is subtracted

If the second string had an extra 'x' character, what would happen in the execution_table?

A The count map would have a negative value for 'x'

B The function would return false immediately when processing 'x'

C The counts would all be zero

D The function would return true

💡 Hint

Refer to key_moments about what happens if a character is missing in count map

Concept Snapshot

Anagram Check Techniques:
- Check if strings have equal length first
- Method 1: Sort both strings and compare
- Method 2: Count characters in first string, subtract counts using second
- If all counts zero at end, strings are anagrams
- Return true if anagram, false otherwise

Full Transcript

This visualization shows how to check if two strings are anagrams. First, we verify if their lengths are equal. Then, we count characters in the first string and store counts in a map. Next, we subtract counts for each character in the second string. If any count goes below zero or a character is missing, the strings are not anagrams. If all counts return to zero, the strings are anagrams. The execution table tracks each step, showing how the count map changes. Key moments clarify why length check is important, why subtraction is done, and what happens if characters mismatch. The quiz tests understanding of count map states and failure conditions.

Practice

1. What does it mean if two strings are anagrams of each other?

easy

A. They contain the same characters in any order

B. They have the same length but different characters

C. They start with the same character

D. They end with the same character

Solution

1. Step 1: Understand the definition of anagrams

   Anagrams are words or phrases made by rearranging the letters of another, so they must have the same characters.

2. Step 2: Compare the character sets

   If two strings have exactly the same characters, just in different orders, they are anagrams.

3. Final Answer:

   They contain the same characters in any order -> Option A

4. Quick Check:

   Anagrams = same characters [OK]

Hint: Check if sorted strings match to confirm anagrams [OK]

Common Mistakes:

• Thinking same length means anagrams
• Only comparing first or last characters
• Ignoring character counts

2. Which TypeScript code snippet correctly checks if two strings are anagrams by sorting?

easy

A. const isAnagram = (a: string, b: string) => a.split('').sort().join('') === b.split('').sort().join('');

B. const isAnagram = (a: string, b: string) => a.split('').sort() === b.split('').sort();

C. const isAnagram = (a: string, b: string) => a.sort() === b.sort();

D. const isAnagram = (a: string, b: string) => a === b;

Solution

1. Step 1: Understand string sorting in TypeScript

   Strings must be split into arrays, sorted, then joined back to strings for comparison.

2. Step 2: Identify correct syntax

   const isAnagram = (a: string, b: string) => a.split('').sort().join('') === b.split('').sort().join(''); correctly splits, sorts, and joins both strings before comparing.

3. Final Answer:

   const isAnagram = (a: string, b: string) => a.split('').sort().join('') === b.split('').sort().join(''); -> Option A

4. Quick Check:

   Sort and join strings before compare [OK]

Hint: Always join after sorting arrays to compare strings [OK]

Common Mistakes:

• Comparing arrays directly without join
• Trying to sort strings directly
• Comparing strings without sorting

3. What is the output of this TypeScript code?

function areAnagrams(s1: string, s2: string): boolean {
  const normalize = (str: string) => str.toLowerCase().replace(/\s+/g, '').split('').sort().join('');
  return normalize(s1) === normalize(s2);
}

console.log(areAnagrams('Listen', 'Silent'));
console.log(areAnagrams('Hello', 'Olelh'));
console.log(areAnagrams('Test', 'Taste'));

medium

A. true false false

B. true true false

C. false true true

D. false false true

Solution

1. Step 1: Normalize strings by lowercasing, removing spaces, sorting

   'Listen' and 'Silent' normalize to 'eilnst', 'Hello' and 'Olelh' normalize to 'ehllo', 'Test' and 'Taste' normalize to 'estt' and 'aestt' respectively.

2. Step 2: Compare normalized strings

   'Listen' vs 'Silent' match (true), 'Hello' vs 'Olelh' match (true), 'Test' vs 'Taste' do not match (false).

3. Final Answer:

   true true false -> Option B

4. Quick Check:

   Normalized strings equal means true [OK]

Hint: Normalize strings before comparing for anagram check [OK]

Common Mistakes:

• Ignoring case differences
• Not removing spaces
• Not sorting characters

4. Identify the bug in this TypeScript function that checks anagrams:

function isAnagram(a: string, b: string): boolean {
  return a.split('').sort() === b.split('').sort();
}

medium

A. Not removing spaces before comparison

B. Missing toLowerCase() for case-insensitive check

C. Comparing arrays directly instead of strings

D. Using split() without arguments

Solution

1. Step 1: Understand array comparison in TypeScript

   Arrays compared with === check reference, not content, so two sorted arrays won't be equal even if same elements.

2. Step 2: Fix by joining arrays to strings before comparing

   Joining sorted arrays to strings allows content comparison, fixing the bug.

3. Final Answer:

   Comparing arrays directly instead of strings -> Option C

4. Quick Check:

   Arrays need join() before compare [OK]

Hint: Join sorted arrays before comparing for equality [OK]

Common Mistakes:

• Comparing arrays with ===
• Ignoring case sensitivity
• Not trimming spaces

5. Given two strings, how can you efficiently check if they are anagrams using a character count map in TypeScript? Which code snippet correctly implements this?

hard

A. function isAnagram(a: string, b: string): boolean {
if (a.length !== b.length) return false;
const count: Record = {};
for (const char of a) count[char] = (count[char] || 0) + 1;
for (const char of b) {
if (!count[char]) return false;
count[char]--;
}
return true;
}

B. function isAnagram(a: string, b: string): boolean {
return a.split('').sort().join('') === b.split('').sort().join('');
}

C. function isAnagram(a: string, b: string): boolean {
return a.length === b.length;
}

D. function isAnagram(a: string, b: string): boolean {
const mapA = new Map();
for (const c of a) mapA.set(c, (mapA.get(c) || 0) + 1);
for (const c of b) mapA.set(c, (mapA.get(c) || 0) - 1);
return [...mapA.values()].every(v => v === 0);
}

Solution

1. Step 1: Understand character count map approach

   Count characters in first string, subtract counts using second string, then check all counts zero.

2. Step 2: Analyze each option

   function isAnagram(a: string, b: string): boolean { if (a.length !== b.length) return false; const count: Record = {}; for (const char of a) count[char] = (count[char] || 0) + 1; for (const char of b) { if (!count[char]) return false; count[char]--; } return true; } misses checking if count goes negative; function isAnagram(a: string, b: string): boolean { return a.split('').sort().join('') === b.split('').sort().join(''); } uses sorting (correct but not map); function isAnagram(a: string, b: string): boolean { return a.length === b.length; } only checks length; function isAnagram(a: string, b: string): boolean { const mapA = new Map(); for (const c of a) mapA.set(c, (mapA.get(c) || 0) + 1); for (const c of b) mapA.set(c, (mapA.get(c) || 0) - 1); return [...mapA.values()].every(v => v === 0); } correctly uses Map to count and verify zero counts.

3. Final Answer:

   Option D correctly implements character count map with Map and zero check -> Option D

4. Quick Check:

   Map counts increment/decrement, all zero means anagram [OK]

Hint: Use map to count chars, decrement, then check all zero [OK]

Common Mistakes:

• Not checking for negative counts
• Only comparing lengths
• Using sorting instead of counting