Palindrome Pairs

▶

Steps

setup

Initialize Trie Root

Create the root node of the trie with empty children, index -1, and empty palindrome suffix list.

💡 The root node is the starting point for all insertions and searches in the trie.

Line:

root = TrieNode()

💡 A single root node is needed to build the trie structure for all reversed words.

insert

Insert reversed 'abcd' (word 0) into trie, char 'd'

Start inserting reversed 'abcd' which is 'dcba'. Insert character 'd' at root's children.

💡 Inserting reversed words allows matching suffixes of original words during search.

Line:

for i, ch in enumerate(reversed(word)):
    if ch not in node.children:
        node.children[ch] = TrieNode()

💡 Trie grows by adding nodes for characters not yet present, building reversed word paths.

insert

Insert reversed 'abcd' (word 0), char 'c'

Insert next character 'c' under node for 'd'. Check if prefix is palindrome for suffix tracking.

💡 Checking palindrome prefixes helps store indices for suffixes that form palindromes.

Line:

if is_palindrome(word[:len(word)-i]):
    node.palindrome_suffixes.append(index)

💡 Only palindrome prefixes cause suffix indices to be stored for later pair matching.

insert

Insert reversed 'abcd' (word 0), char 'b'

Insert character 'b' under node for 'c'. Check palindrome prefix for suffix tracking.

💡 Continuing insertion, palindrome checks ensure suffix indices are stored correctly.

Line:

if is_palindrome(word[:len(word)-i]):
    node.palindrome_suffixes.append(index)

💡 Only palindrome prefixes add indices to suffix lists, pruning unnecessary pairs.

insert

Insert reversed 'abcd' (word 0), char 'a' and mark index

Insert last character 'a' under node 'b'. Mark this node's index as 0 and add index to palindrome_suffixes.

💡 Marking index at end node identifies complete reversed word for matching during search.

Line:

node.index = index
node.palindrome_suffixes.append(index)

💡 End nodes store word indices and palindrome suffix info for efficient pair detection.

insert

Insert reversed 'dcba' (word 1), char 'a'

Start inserting reversed 'dcba' which is 'abcd'. Insert character 'a' at root's children.

💡 Inserting next reversed word builds trie branches for matching prefixes.

Line:

for i, ch in enumerate(reversed(word)):
    if ch not in node.children:
        node.children[ch] = TrieNode()

💡 Trie branches grow as new reversed words introduce new prefixes.

insert

Insert reversed 'dcba' (word 1), char 'b'

Insert character 'b' under node 'a'. Check palindrome prefix for suffix tracking.

💡 Palindrome prefix checks continue to identify suffix indices.

Line:

if is_palindrome(word[:len(word)-i]):
    node.palindrome_suffixes.append(index)

💡 Only palindrome prefixes add indices to suffix lists.

insert

Insert reversed 'dcba' (word 1), char 'c'

Insert character 'c' under node 'b'. Check palindrome prefix for suffix tracking.

💡 Continuing insertion with palindrome suffix checks.

Line:

if is_palindrome(word[:len(word)-i]):
    node.palindrome_suffixes.append(index)

💡 Only palindrome prefixes add indices to suffix lists.

insert

Insert reversed 'dcba' (word 1), char 'd' and mark index

Insert last character 'd' under node 'c'. Mark node index as 1 and add to palindrome_suffixes.

💡 Marking end node with word index for matching during search.

Line:

node.index = index
node.palindrome_suffixes.append(index)

💡 End nodes identify complete reversed words for pair matching.

search

Search for palindrome pairs with word 'abcd' (index 0), char 'a'

Start searching trie with 'abcd'. At root, check if node index is valid and if suffix 'abcd' is palindrome.

💡 Searching tries to find matching reversed prefixes and palindrome suffixes.

Line:

if node.index >= 0 and node.index != index and is_palindrome(word[i:]):
    res.append([index, node.index])

💡 Pairs are added only when node index differs and suffix is palindrome.

search

Search with word 'abcd' (index 0), char 'b'

Move to child node for 'a'. Check if node index valid and suffix 'bcd' palindrome.

💡 Checking palindrome suffixes at each step helps find pairs early.

Line:

if node.index >= 0 and node.index != index and is_palindrome(word[i:]):
    res.append([index, node.index])

💡 No pair found yet, continue traversal.

search

Search with word 'abcd' (index 0), char 'c'

Move to child node for 'b'. Check if node index valid and suffix 'cd' palindrome.

💡 Continuing search to find matching reversed prefixes.

Line:

if node.index >= 0 and node.index != index and is_palindrome(word[i:]):
    res.append([index, node.index])

💡 No pair found yet, continue traversal.

search

Search with word 'abcd' (index 0), char 'd'

Move to child node for 'c'. Check if node index valid and suffix 'd' palindrome.

💡 At last character, check for palindrome suffixes to add pairs.

Line:

if node.index >= 0 and node.index != index and is_palindrome(word[i:]):
    res.append([index, node.index])

💡 Found palindrome pair by matching reversed prefix and palindrome suffix.

search

Add pairs from palindrome_suffixes at node after full traversal of 'abcd'

After full traversal, add pairs from palindrome_suffixes stored at current node excluding current word index.

💡 Palindrome suffix indices at end node represent words that form palindrome pairs.

Line:

for j in node.palindrome_suffixes:
    if j != index:
        res.append([index, j])

💡 Palindrome suffixes at end node help find pairs with empty suffix.

search

Search for palindrome pairs with word 'dcba' (index 1), char 'd'

Start searching trie with 'dcba'. At root, check if node index valid and suffix 'dcba' palindrome.

💡 Searching for pairs with second word to find reverse pairs.

Line:

if node.index >= 0 and node.index != index and is_palindrome(word[i:]):
    res.append([index, node.index])

💡 Search continues to find matching reversed prefixes.

search

Search with word 'dcba' (index 1), char 'c'

Move to child node for 'd'. Check if node index valid and suffix 'cba' palindrome.

💡 Continuing search for matching reversed prefixes.

Line:

if node.index >= 0 and node.index != index and is_palindrome(word[i:]):
    res.append([index, node.index])

💡 No pair found yet, continue traversal.

search

Search with word 'dcba' (index 1), char 'b'

Move to child node for 'c'. Check if node index valid and suffix 'ba' palindrome.

💡 Continuing search for palindrome pairs.

Line:

if node.index >= 0 and node.index != index and is_palindrome(word[i:]):
    res.append([index, node.index])

💡 No pair found yet, continue traversal.

search

Search with word 'dcba' (index 1), char 'a'

Move to child node for 'b'. Check if node index valid and suffix 'a' palindrome.

💡 At last character, check for palindrome suffixes to add pairs.

Line:

if node.index >= 0 and node.index != index and is_palindrome(word[i:]):
    res.append([index, node.index])

💡 Found palindrome pair by matching reversed prefix and palindrome suffix.

search

Add pairs from palindrome_suffixes at node after full traversal of 'dcba'

After full traversal, add pairs from palindrome_suffixes stored at current node excluding current word index.

💡 Palindrome suffix indices at end node represent words that form palindrome pairs.

Line:

for j in node.palindrome_suffixes:
    if j != index:
        res.append([index, j])

💡 Palindrome suffixes at end node help find pairs with empty suffix.

reconstruct

Final result after processing all words

After inserting all words and searching for pairs, the final palindrome pairs are collected.

💡 The final pairs represent all palindrome pairs found by the algorithm.

Line:

return result

💡 The algorithm efficiently finds palindrome pairs using trie and palindrome suffix tracking.

class TrieNode:
    def __init__(self):
        self.children = {}  # STEP 1
        self.index = -1
        self.palindrome_suffixes = []

def is_palindrome(word):
    return word == word[::-1]

def palindromePairs(words):
    root = TrieNode()  # STEP 1

    def add_word(word, index):
        node = root
        for i, ch in enumerate(reversed(word)):
            if is_palindrome(word[:len(word)-i]):  # STEP 2-5
                node.palindrome_suffixes.append(index)
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.index = index  # STEP 5
        node.palindrome_suffixes.append(index)

    def search(word, index):
        res = []
        node = root
        for i, ch in enumerate(word):
            if node.index >= 0 and node.index != index and is_palindrome(word[i:]):  # STEP 10-19
                res.append([index, node.index])
            if ch not in node.children:
                return res
            node = node.children[ch]
        for j in node.palindrome_suffixes:
            if j != index:
                res.append([index, j])
        return res

    for i, word in enumerate(words):
        add_word(word, i)  # STEP 2-9

    result = []
    for i, word in enumerate(words):
        result.extend(search(word, i))  # STEP 10-19
    return result  # STEP 20

if __name__ == '__main__':
    words = ["abcd","dcba","lls","s","sssll"]
    print(palindromePairs(words))

📊

Palindrome Pairs - Watch the Algorithm Execute, Step by Step

Watching the trie construction and search step-by-step reveals how palindrome suffixes are used to efficiently find pairs without brute force checks.

setup

abcd

0

dcba

1

lls

2

s

3

sssll

4

Result: []

insert

node

abcd

0

dcba

1

lls

2

s

3

sssll

4

Result: []

insert

abcd

0

node

dcba

1

lls

2

s

3

sssll

4

Result: []

insert

abcd

0

dcba

1

node

lls

2

s

3

sssll

4

Result: []

insert

abcd

0

dcba

1

lls

2

node

s

3

sssll

4

Result: []

insert

node

abcd

0

dcba

1

lls

2

s

3

sssll

4

Result: []

insert

abcd

0

dcba

1

lls

2

s

3

node

sssll

4

Result: []

insert

abcd

0

dcba

1

lls

2

s

3

sssll

4

Result: []

insert

abcd

0

dcba

1

lls

2

s

3

sssll

4

Result: []

compare

node

abcd

0

dcba

1

lls

2

s

3

sssll

4

Result: []

compare

abcd

0

i

dcba

1

lls

2

s

3

node

sssll

4

Result: []

compare

abcd

0

dcba

1

i

lls

2

s

3

sssll

4

Result: []

compare

abcd

0

dcba

1

lls

2

i

s

3

sssll

4

Result: [[0,1]]

record

abcd

0

dcba

1

lls

2

s

3

sssll

4

Result: [[0,1]]

compare

node

abcd

0

dcba

1

lls

2

s

3

sssll

4

Result: [[0,1]]

compare

abcd

0

node

dcba

1

lls

2

s

3

sssll

4

Result: [[0,1]]

compare

abcd

0

dcba

1

i

lls

2

s

3

sssll

4

Result: [[0,1]]

compare

abcd

0

dcba

1

lls

2

i

s

3

sssll

4

Result: [[0,1],[1,0]]

record

abcd

0

dcba

1

lls

2

s

3

sssll

4

Result: [[0,1],[1,0]]

reconstruct

abcd

0

dcba

1

lls

2

s

3

sssll

4

Result: [[0,1],[1,0],[3,2],[2,4]]

Key Takeaways

✓ Building a trie with reversed words and storing palindrome suffix indices enables efficient palindrome pair detection.

This insight is hard to see from code alone because it involves understanding how suffix palindrome checks prune the search space.

✓ During search, checking if the remaining substring is a palindrome at nodes with valid indices reveals pairs early.

Visualizing pointer movement and palindrome checks clarifies why some pairs are found before full traversal.

✓ Palindrome suffix lists at trie nodes allow pairing words with empty suffixes or overlapping palindromes.

Seeing these lists in the trie structure helps understand how the algorithm handles complex palindrome cases.

Practice

1. You need to design a cache system that evicts the least frequently used items first, and among those with the same frequency, evicts the least recently used. Which algorithmic approach best guarantees optimal eviction behavior for this problem?

easy

A. Maintain frequency counts and timestamps for each item, evicting the item with the lowest frequency and oldest timestamp when needed.

B. Sort all cache items by their values and evict the item with the smallest value when capacity is full.

C. Use a standard LRU cache eviction policy based on recency only, ignoring frequency counts.

D. Use a simple FIFO queue to evict the oldest inserted item when capacity is reached.

Solution

1. Step 1: Understand eviction criteria

   The problem requires evicting the least frequently used item first, and if multiple items share the same frequency, evict the least recently used among them.

2. Step 2: Identify approach that tracks frequency and recency

   Only an approach that maintains both frequency counts and timestamps can correctly identify the LFU and LRU items for eviction.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Eviction based on frequency and recency -> correct LFU cache behavior [OK]

Hint: LFU needs frequency + recency tracking [OK]

Common Mistakes:

• Confusing LFU with LRU eviction policy
• Using FIFO which ignores frequency
• Sorting by value instead of usage metrics

2. You are given an array nums and multiple queries, each query containing two integers x and m. For each query, you want to find the maximum XOR of x with any element in nums that is less than or equal to m. Which algorithmic approach guarantees an optimal solution for large inputs?

easy

A. Greedy approach selecting the largest element less than or equal to m for XOR

B. Brute force nested loops checking all pairs for each query

C. Dynamic programming with memoization over all possible XOR values

D. Sorting nums and queries, then using a bitwise trie with offline queries and two pointers

Solution

1. Step 1: Understand problem constraints

   Brute force is too slow for large inputs; greedy fails because max element ≤ m does not guarantee max XOR.

2. Step 2: Identify optimal approach

   Sorting and offline queries allow incremental trie insertion of eligible elements, enabling efficient max XOR queries.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Sorting + trie + offline queries is known optimal [OK]

Hint: Offline queries + trie + sorting -> optimal [OK]

Common Mistakes:

• Assuming greedy max element ≤ m yields max XOR
• Trying DP over XOR values
• Using brute force for large inputs

3. You need to place n queens on an nxn chessboard so that no two queens threaten each other. Which algorithmic approach guarantees finding all valid configurations efficiently by pruning invalid partial solutions early?

easy

A. Backtracking that tries all column positions per row and prunes invalid placements using sets or bitmasks

B. Greedy algorithm that places queens row by row choosing the first safe column

C. Dynamic programming that stores subproblems of partial queen placements by rows and columns

D. Divide and conquer by splitting the board into smaller sub-boards and solving independently

Solution

1. Step 1: Understand problem constraints

   The problem requires placing queens so none attack each other, which involves checking columns and diagonals.

2. Step 2: Identify approach that prunes invalid states

   Backtracking tries all placements but prunes invalid ones early using sets or bitmasks, guaranteeing all solutions without brute force.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Backtracking with pruning is standard for N-Queens [OK]

Hint: Backtracking prunes invalid queen placements early [OK]

Common Mistakes:

• Thinking greedy placement always works
• Confusing DP with backtracking
• Assuming independent subproblems in divide and conquer

4. You are given a list of envelopes, each with a width and height. You want to find the maximum number of envelopes you can nest inside each other such that each envelope fits strictly inside the next one by both width and height. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Greedy approach by sorting envelopes by width and picking the tallest envelope at each step.

B. Sort envelopes by width ascending and height descending, then find the Longest Increasing Subsequence (LIS) on heights using binary search.

C. Dynamic programming with a 2D table tracking all pairs of envelopes to find the longest chain.

D. Use a graph and find the longest path by topological sorting.

Solution

1. Step 1: Understand problem constraints

   The problem requires strict increasing order in both width and height for nesting envelopes.

2. Step 2: Identify optimal approach

   Sorting by width ascending and height descending ensures envelopes with the same width do not interfere. Then LIS on heights finds the longest chain efficiently.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Sorting + LIS with binary search is the known optimal approach [OK]

Hint: Sort width asc, height desc, then LIS on heights [OK]

Common Mistakes:

• Using greedy picking tallest envelope only
• Applying LIS on widths instead of heights
• Using DP without sorting properly

5. Suppose the problem is modified so that you can buy and sell the same stock multiple times on the same day (i.e., transactions can overlap or reuse the same day). Which modification to the DP approach correctly handles this variant?

hard

A. Increase the DP state dimension to track the number of transactions per day and allow multiple buys/sells on the same day

B. Remove the holding state and allow buying and selling at the same index in the DP transitions

C. Use the original DP but allow t to increment multiple times per day to simulate overlapping transactions

D. Switch to a greedy approach summing all positive price differences, ignoring transaction limits

Solution

1. Step 1: Understand the variant's implication

   Allowing multiple buys and sells on the same day means the holding state is no longer needed to prevent overlapping transactions.

2. Step 2: Modify DP transitions accordingly

   Removing the holding state and allowing buy and sell transitions at the same day index enables modeling multiple transactions per day correctly.

3. Step 3: Evaluate other options

   Increasing DP dimensions adds unnecessary complexity; incrementing t multiple times per day breaks the transaction count logic; greedy ignores transaction limits and is incorrect.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Removing holding state fits the relaxed constraint of multiple transactions per day [OK]

Hint: Relax holding state to allow multiple same-day transactions [OK]

Common Mistakes:

• Trying to track multiple transactions per day with extra DP dimensions
• Misusing transaction count increments
• Switching to greedy ignoring constraints