Isomorphic Strings

▶

Steps

setup

Check Lengths of Strings

The algorithm compares the lengths of s and t. Since both have length 3, it proceeds.

💡 If lengths differ, strings cannot be isomorphic, so this quick check avoids unnecessary work.

Line:

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

💡 Length equality is a necessary condition for isomorphism.

setup

Initialize Empty Hash Maps

Two empty hash maps, s_to_t and t_to_s, are created to store character mappings from s to t and t to s respectively.

💡 Separate maps ensure the mapping is bijective and consistent in both directions.

Line:

s_to_t = {}
t_to_s = {}

💡 Empty maps prepare the algorithm to record character correspondences.

traverse

Process First Character Pair ('e', 'a') in s_to_t

Check if 'e' is in s_to_t. It's not, so insert mapping 'e' -> 'a'.

💡 First encounter of 'e' means we create a new mapping to 'a'.

Line:

if c1 in s_to_t:
    if s_to_t[c1] != c2:
        return False
else:
    s_to_t[c1] = c2

💡 New character from s maps to new character from t.

traverse

Process First Character Pair ('e', 'a') in t_to_s

Check if 'a' is in t_to_s. It's not, so insert mapping 'a' -> 'e'.

💡 Ensure the reverse mapping is also recorded for consistency.

Line:

if c2 in t_to_s:
    if t_to_s[c2] != c1:
        return False
else:
    t_to_s[c2] = c1

💡 Reverse mapping confirms bijection.

traverse

Process Second Character Pair ('g', 'd') in s_to_t

Check if 'g' is in s_to_t. It's not, so insert mapping 'g' -> 'd'.

💡 New character 'g' from s maps to new character 'd' from t.

Line:

if c1 in s_to_t:
    if s_to_t[c1] != c2:
        return False
else:
    s_to_t[c1] = c2

💡 Mapping continues to build without conflict.

traverse

Process Second Character Pair ('g', 'd') in t_to_s

Check if 'd' is in t_to_s. It's not, so insert mapping 'd' -> 'g'.

💡 Reverse mapping for 'd' ensures consistency.

Line:

if c2 in t_to_s:
    if t_to_s[c2] != c1:
        return False
else:
    t_to_s[c2] = c1

💡 Reverse map grows consistently.

traverse

Process Third Character Pair ('g', 'd') in s_to_t

Check if 'g' is in s_to_t. It is, and maps to 'd', which matches current character in t.

💡 Existing mapping matches, so no conflict.

Line:

if c1 in s_to_t:
    if s_to_t[c1] != c2:
        return False

💡 Repeated characters must map to the same character.

traverse

Process Third Character Pair ('g', 'd') in t_to_s

Check if 'd' is in t_to_s. It is, and maps to 'g', matching current character in s.

💡 Reverse mapping also consistent, confirming bijection.

Line:

if c2 in t_to_s:
    if t_to_s[c2] != c1:
        return False

💡 Both maps agree on character correspondence.

reconstruct

All Character Pairs Processed, Confirm No Conflicts

No inconsistencies found in any mapping after processing all pairs; the strings remain isomorphic.

💡 At this point, the algorithm has verified all character mappings are consistent.

Line:

return True

💡 The algorithm confirms isomorphism by consistent bidirectional mappings.

reconstruct

Return True as Final Answer

The algorithm returns True, indicating the input strings are isomorphic.

💡 Returning True confirms the successful one-to-one character mapping.

Line:

return True

💡 The final output reflects the consistent mappings found.

def isIsomorphic(s: str, t: str) -> bool:
    # STEP 1: Check lengths
    if len(s) != len(t):
        return False
    # STEP 2: Initialize maps
    s_to_t = {}
    t_to_s = {}
    # STEP 3-8: Iterate pairs
    for c1, c2 in zip(s, t):
        # STEP 3-4: Check s_to_t
        if c1 in s_to_t:
            if s_to_t[c1] != c2:
                return False
        else:
            s_to_t[c1] = c2
        # STEP 5-6: Check t_to_s
        if c2 in t_to_s:
            if t_to_s[c2] != c1:
                return False
        else:
            t_to_s[c2] = c1
    # STEP 9-10: Return True
    return True

📊

Isomorphic Strings - Watch the Algorithm Execute, Step by Step

Watching each character pair processed and how the maps update or validate mappings reveals the core logic of isomorphic string checking more clearly than reading code alone.

check

empty map

insert

empty map

insert

Lookup: e

e→"a"lookup

insert

Lookup: a

a→"e"lookup

insert

Lookup: g

e→"a"

g→"d"lookup

insert

Lookup: d

a→"e"

d→"g"lookup

lookup

Lookup: g→ "d"

e→"a"

g→"d"lookup

lookup

Lookup: d→ "g"

a→"e"

d→"g"lookup

check

e→"a"

g→"d"

a→"e"

d→"g"

check

e→"a"

g→"d"

a→"e"

d→"g"

Result: true

Key Takeaways

✓ Bidirectional hash maps ensure a one-to-one character mapping between the two strings.

This is hard to see from code alone because the dual checks happen separately but must be consistent simultaneously.

✓ Each character pair is processed individually, either inserting a new mapping or validating an existing one.

Visualizing each insertion and lookup clarifies how conflicts are detected early.

✓ Repeated characters must map to the same character, enforcing consistency across the entire string.

Seeing the lookup hits for repeated characters helps understand why inconsistent mappings cause failure.

Practice

1. Given the following code, what is the return value when the input string is "aabc"?

easy

A. 2

B. 1

C. -1

D. 0

Solution

1. Step 1: Trace frequency and first_index dictionaries

   For "aabc": freq={'a':2, 'b':1, 'c':1}, first_index={'a':0, 'b':2, 'c':3}

2. Step 2: Find minimum index with frequency 1

   Characters with count 1 are 'b' at index 2 and 'c' at index 3; minimum is 2.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   First unique char is 'b' at index 2 [OK]

Hint: Check frequency and first occurrence carefully [OK]

Common Mistakes:

• Returning character instead of index
• Off-by-one index errors
• Ignoring multiple unique chars

2. You are given an integer array and need to find the k elements that appear most frequently. Which algorithmic approach guarantees an optimal solution with linear time complexity?

easy

A. Use a frequency map and bucket sort to group elements by their frequency, then collect top k from highest frequency buckets.

B. Sort the entire array and pick the top k elements by frequency.

C. Use a greedy approach that picks elements as they appear until k elements are chosen.

D. Use dynamic programming to build frequency counts and select top k elements.

Solution

1. Step 1: Understand problem constraints

   The problem requires finding top k frequent elements efficiently, ideally in linear time.

2. Step 2: Identify approach with linear time complexity

   Bucket sort groups elements by frequency, allowing O(n) time retrieval of top k elements by scanning buckets from high to low frequency.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Bucket sort approach is known to run in O(n) time for this problem [OK]

Hint: Bucket sort groups by frequency for O(n) retrieval [OK]

Common Mistakes:

• Sorting entire array is O(n log n), not optimal
• Greedy approach ignores frequency counts
• DP is unrelated to frequency counting here

3. What is the time complexity of the optimal bucket sort approach for finding the top k frequent elements in an array of size n with u unique elements?

medium

A. O(n + u) since building frequency map and buckets takes linear time

B. O(n log n) due to sorting the frequency map keys

C. O(u * log u) because sorting unique elements is required

D. O(n) because frequency counting and bucket filling are linear in n

Solution

1. Step 1: Analyze frequency counting

   Counting frequencies requires iterating over n elements -> O(n)

2. Step 2: Analyze bucket filling and result collection

   Filling buckets and collecting top k elements is O(n) since total frequencies sum to n, plus O(u) for iterating unique elements.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Complexity is O(n + u), which is linear since u ≤ n [OK]

Hint: Frequency counting + bucket filling is linear [OK]

Common Mistakes:

• Assuming sorting unique keys is needed
• Confusing n with u in complexity
• Ignoring that bucket iteration is linear in total elements

4. Suppose the problem changes: now you want to detect if any number appears at least twice, but the array is extremely large and cannot fit into memory. Which approach is best suited to handle this scenario?

hard

A. Sort the array externally (external sort) and then scan for duplicates in a streaming fashion.

B. Use a hash set in memory as before, but process the array in chunks and merge results.

C. Use a bloom filter to probabilistically detect duplicates with limited memory.

D. Use nested loops on the entire array since it requires no extra space.

Solution

1. Step 1: Understand memory constraints

   The array is too large to fit in memory, so hash sets or sorting in memory are infeasible.

2. Step 2: Evaluate options

   External sorting is possible and practical for large data sets that cannot fit into memory. Bloom filters provide probabilistic detection but can yield false positives, which may not be acceptable depending on requirements. Nested loops are impractical due to O(n²) time complexity.

3. Step 3: Choose external sorting

   External sorting allows sorting data on disk and then scanning sequentially for duplicates, which is efficient and exact.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   External sorting handles large data sets with limited memory and provides exact duplicate detection [OK]

Hint: External sorting enables exact duplicate detection on large data sets [OK]

Common Mistakes:

• Assuming hash sets can handle huge data
• Ignoring external sorting costs
• Choosing nested loops despite inefficiency
• Overlooking bloom filter false positives

5. Suppose the time-based key-value store is extended to allow multiple values to be set at the same timestamp for a key, and get should return the most recently set value at or before the timestamp. Which modification to the data structure and retrieval algorithm is correct?

hard

A. Store multiple values per timestamp in a list and modify binary search to find the last value in that list.

B. Store timestamps with duplicates in a list and use bisect_right to find insertion index, then return the last inserted value at that timestamp.

C. Store all (timestamp, value) pairs in insertion order and perform linear search backward on get.

D. Use a hash map from (key, timestamp) to a stack of values and pop on get.

Solution

1. Step 1: Understand requirement for multiple values per timestamp

   Multiple values at same timestamp require storing duplicates and retrieving the most recent one.

2. Step 2: Analyze retrieval with duplicates

   Using bisect_right on timestamps list with duplicates returns insertion index after all duplicates; returning value at i-1 gives the last inserted value at that timestamp.

3. Step 3: Confirm data structure modification

   Storing timestamps with duplicates in order and values aligned allows correct retrieval without linear search or complex structures.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   bisect_right with duplicates returns correct index for last inserted value [OK]

Hint: bisect_right handles duplicates by returning insertion after last duplicate [OK]

Common Mistakes:

• Using linear search causing inefficiency
• Using stacks requiring pop on get
• Storing multiple values in nested lists complicates retrieval