LeetCode 3093 - Longest Common Suffix Queries

LeetCode Problem 3093

Difficulty: 🔴 Hard
Topics: Array, String, Trie

Solution

Problem Understanding

The problem asks us to process a set of suffix matching queries efficiently.

We are given two arrays:

• wordsContainer, which contains candidate strings
• wordsQuery, which contains query strings

For every query string, we must find the index of the string in wordsContainer that shares the longest common suffix with that query.

A suffix is the ending portion of a string. For example:

• "bcd" is a suffix of "abcd"
• "cd" is a suffix of "abcd"
• "xyz" is not a suffix of "abcd"

The matching process has three levels of priority:

1. Maximize the length of the common suffix
2. If multiple strings share the same longest suffix, choose the shortest string
3. If there is still a tie, choose the earliest occurrence in wordsContainer

The output is an integer array where each element is the index of the chosen string for the corresponding query.

The constraints are extremely important:

• Up to 10^4 words in each array
• Total character count can reach 5 * 10^5

This immediately tells us that an algorithm comparing every query against every container word character by character will be too slow. We need something closer to linear complexity in the total input size.

An important observation is that suffix matching becomes prefix matching if we reverse the strings. For example:

• "abcd" becomes "dcba"
• "bcd" becomes "dcb"

Now the common suffix "bcd" becomes the common prefix "dcb".

This transformation strongly suggests using a Trie, because Tries are optimized for prefix matching.

There are several edge cases worth noting immediately:

• A query may share no suffix at all with any container word. In that case, the answer should still be the globally shortest word in wordsContainer.
• Multiple container words may be identical.
• Very short words and very long words may coexist.
• Queries may be longer than all container words.
• Tie breaking by shortest length and earliest index must be handled consistently at every level of traversal.

Approaches

Brute Force Approach

The most direct solution is to compare every query against every word in wordsContainer.

For each pair of strings:

1. Start from the end of both strings
2. Count how many characters match moving backward
3. Keep track of the best suffix length found so far
4. Apply tie breaking rules when suffix lengths are equal

This approach is straightforward and guaranteed to work correctly because it explicitly computes the suffix match length for every possible candidate.

However, the complexity becomes far too large.

If we have:

• N container words
• Q query words
• average string length L

Then the complexity is approximately:

O(N * Q * L)

Given the constraints, this can easily exceed billions of operations.

Optimal Approach, Reversed Trie

The key insight is that suffix matching can be transformed into prefix matching by reversing all strings.

For example:

Original	Reversed
"abcd"	"dcba"
"bcd"	"dcb"

Now, instead of finding the longest common suffix, we only need to find the longest common prefix.

A Trie is perfect for this because:

• Each node represents a prefix
• Traversing the Trie naturally finds the longest matching prefix
• Query time becomes proportional only to the query length

The important additional trick is storing, at every Trie node, the best candidate index according to the tie breaking rules.

That means each node stores:

• the shortest word passing through that node
• if tied, the earliest index

This allows us to answer queries immediately after traversal.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(N * Q * L)	O(1)	Compare every query against every word
Optimal Trie	O(totalContainerChars + totalQueryChars)	O(totalContainerChars)	Reverse strings and use Trie prefix matching

Algorithm Walkthrough

1. Reverse the perspective from suffixes to prefixes

A suffix comparison from the end of strings is awkward for a Trie.

Instead, reverse every string:

• "abcd" becomes "dcba"
• "bcd" becomes "dcb"

Now longest common suffix becomes longest common prefix.

2. Build a Trie from reversed container words

We insert every reversed container word into the Trie character by character.

Each Trie node contains:

• children, mapping characters to child nodes
• best_index, the best candidate word index for this node

The best_index is determined by:

1. Shortest word length
2. Earliest index if lengths are equal

This information is updated during insertion.

3. Store the globally best candidate at the root

The root represents the empty prefix.

This corresponds to the empty suffix case.

If a query shares no suffix at all with any word, traversal stops immediately and we return the root's stored index.

4. Insert words carefully

When inserting a word:

1. Start at the root
2. Update the root's best candidate if needed
3. Traverse each reversed character
4. Create child nodes as necessary
5. Update each node's best candidate

This ensures every node knows the optimal answer for that suffix.

5. Process queries

For each query:

1. Reverse the query
2. Start at the Trie root
3. Traverse while matching characters exist
4. Stop at the deepest matching node
5. Return that node's stored index

The deepest reachable node corresponds to the longest common suffix.

6. Why tie breaking works automatically

Suppose multiple words share the same suffix.

All such words pass through the same Trie node.

Since each node stores the shortest valid word, with earliest index as secondary tie breaker, the correct answer is already precomputed.

Why it works

Each Trie node represents a reversed prefix, which corresponds to a suffix in the original strings.

During insertion, every node stores the optimal container word among all words sharing that suffix.

During query traversal, the deepest reachable node corresponds exactly to the longest shared suffix. Since the node already stores the best valid candidate according to the tie breaking rules, returning its stored index is always correct.

Python Solution

from typing import List

class TrieNode:
    def __init__(self):
        self.children = {}
        self.best_index = -1

class Solution:
    def stringIndices(self, wordsContainer: List[str], wordsQuery: List[str]) -> List[int]:
        
        root = TrieNode()

        def is_better(candidate_idx: int, current_idx: int) -> bool:
            if current_idx == -1:
                return True

            candidate_len = len(wordsContainer[candidate_idx])
            current_len = len(wordsContainer[current_idx])

            if candidate_len < current_len:
                return True

            if candidate_len == current_len and candidate_idx < current_idx:
                return True

            return False

        # Build Trie using reversed words
        for idx, word in enumerate(wordsContainer):
            reversed_word = word[::-1]

            node = root

            if is_better(idx, node.best_index):
                node.best_index = idx

            for ch in reversed_word:
                if ch not in node.children:
                    node.children[ch] = TrieNode()

                node = node.children[ch]

                if is_better(idx, node.best_index):
                    node.best_index = idx

        result = []

        # Process queries
        for query in wordsQuery:
            reversed_query = query[::-1]

            node = root

            for ch in reversed_query:
                if ch not in node.children:
                    break
                node = node.children[ch]

            result.append(node.best_index)

        return result

The implementation begins with a Trie node definition. Each node stores child pointers and the best container index for the suffix represented by that node.

The is_better() helper function encapsulates the tie breaking logic. It compares two candidate indices and determines whether the new candidate should replace the current one.

During Trie construction, every container word is reversed before insertion. As traversal proceeds through the Trie, every visited node updates its best_index if the current word is a better candidate.

The root node is especially important because it represents the empty suffix. This guarantees correct handling when no characters match.

For query processing, each query is reversed and traversed through the Trie. Traversal continues as long as matching characters exist. The deepest reachable node corresponds to the longest common suffix, and its stored best_index is the answer.

Go Solution

package main

type TrieNode struct {
	children  [26]*TrieNode
	bestIndex int
}

func newTrieNode() *TrieNode {
	return &TrieNode{
		bestIndex: -1,
	}
}

func stringIndices(wordsContainer []string, wordsQuery []string) []int {

	root := newTrieNode()

	isBetter := func(candidateIdx, currentIdx int) bool {
		if currentIdx == -1 {
			return true
		}

		candidateLen := len(wordsContainer[candidateIdx])
		currentLen := len(wordsContainer[currentIdx])

		if candidateLen < currentLen {
			return true
		}

		if candidateLen == currentLen && candidateIdx < currentIdx {
			return true
		}

		return false
	}

	// Build Trie
	for idx, word := range wordsContainer {

		node := root

		if isBetter(idx, node.bestIndex) {
			node.bestIndex = idx
		}

		for i := len(word) - 1; i >= 0; i-- {
			c := word[i] - 'a'

			if node.children[c] == nil {
				node.children[c] = newTrieNode()
			}

			node = node.children[c]

			if isBetter(idx, node.bestIndex) {
				node.bestIndex = idx
			}
		}
	}

	ans := make([]int, len(wordsQuery))

	// Process queries
	for i, query := range wordsQuery {

		node := root

		for j := len(query) - 1; j >= 0; j-- {
			c := query[j] - 'a'

			if node.children[c] == nil {
				break
			}

			node = node.children[c]
		}

		ans[i] = node.bestIndex
	}

	return ans
}

The Go implementation follows the same algorithmic structure as the Python version, but uses a fixed-size array of 26 child pointers instead of a hash map. Since the input contains only lowercase English letters, this is more memory efficient and faster than using a map.

Go does not support default constructors, so a helper newTrieNode() function initializes nodes with bestIndex = -1.

Traversal uses byte arithmetic with 'a' offsets to convert characters into array indices.

No integer overflow concerns exist here because all indices and lengths remain well within Go's standard integer range.

Worked Examples

Example 1

wordsContainer = ["abcd","bcd","xbcd"]
wordsQuery = ["cd","bcd","xyz"]

Step 1, Reverse Container Words

Original	Reversed
abcd	dcba
bcd	dcb
xbcd	dcbx

Step 2, Build Trie

After inserting "abcd":

Node Path	Stored Index
root	0
d	0
dc	0
dcb	0
dcba	0

After inserting "bcd":

Since "bcd" is shorter than "abcd", nodes get updated.

Node Path	Stored Index
root	1
d	1
dc	1
dcb	1
dcba	0

After inserting "xbcd":

No updates occur because "xbcd" is longer than "bcd".

Query "cd"

Reversed query is "dc".

Traversal:

Character	Trie Exists?	Current Node Best Index
d	Yes	1
c	Yes	1

Answer is 1.

Query "bcd"

Reversed query is "dcb".

Traversal reaches node "dcb" whose stored index is 1.

Answer is 1.

Query "xyz"

Reversed query is "zyx".

No child 'z' exists from root.

We remain at root.

Root stores index 1.

Answer is 1.

Final output:

[1, 1, 1]

Example 2

wordsContainer = ["abcdefgh","poiuygh","ghghgh"]
wordsQuery = ["gh","acbfgh","acbfegh"]

Reversed Container Words

Original	Reversed
abcdefgh	hgfedcba
poiuygh	hgyuiop
ghghgh	hghghg

The root stores index 2 because "ghghgh" has shortest length 6.

Query "gh"

Reversed query is "hg".

Traversal:

Character	Node Exists?
h	Yes
g	Yes

Node "hg" stores index 2.

Answer is 2.

Query "acbfgh"

Reversed query is "hgfbca".

Traversal:

Prefix	Exists?
h	Yes
hg	Yes
hgf	Yes
hgfb	No

Deepest match is "hgf".

That node corresponds uniquely to "abcdefgh".

Answer is 0.

Query "acbfegh"

Reversed query is "hgefbca".

Traversal stops after "hg".

Node "hg" stores index 2.

Answer is 2.

Final output:

[2, 0, 2]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(C + Q)	C is total characters in wordsContainer, Q is total characters in wordsQuery
Space	O(C)	Trie stores all container characters

The Trie construction processes every container character exactly once.

Each query traversal also processes each query character at most once before stopping.

Because the total character count across all strings is bounded by 5 * 10^5, the algorithm runs efficiently within the constraints.

The Trie size is proportional to the total number of inserted characters, giving linear space complexity.

Test Cases

from typing import List

class Solution:
    def stringIndices(self, wordsContainer: List[str], wordsQuery: List[str]) -> List[int]:
        
        class TrieNode:
            def __init__(self):
                self.children = {}
                self.best_index = -1

        root = TrieNode()

        def is_better(candidate_idx: int, current_idx: int) -> bool:
            if current_idx == -1:
                return True

            candidate_len = len(wordsContainer[candidate_idx])
            current_len = len(wordsContainer[current_idx])

            if candidate_len < current_len:
                return True

            if candidate_len == current_len and candidate_idx < current_idx:
                return True

            return False

        for idx, word in enumerate(wordsContainer):
            node = root

            if is_better(idx, node.best_index):
                node.best_index = idx

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

                node = node.children[ch]

                if is_better(idx, node.best_index):
                    node.best_index = idx

        result = []

        for query in wordsQuery:
            node = root

            for ch in reversed(query):
                if ch not in node.children:
                    break
                node = node.children[ch]

            result.append(node.best_index)

        return result

sol = Solution()

# Provided example 1
assert sol.stringIndices(
    ["abcd", "bcd", "xbcd"],
    ["cd", "bcd", "xyz"]
) == [1, 1, 1]

# Provided example 2
assert sol.stringIndices(
    ["abcdefgh", "poiuygh", "ghghgh"],
    ["gh", "acbfgh", "acbfegh"]
) == [2, 0, 2]

# Single word container
assert sol.stringIndices(
    ["apple"],
    ["apple", "ple", "x"]
) == [0, 0, 0]

# Tie by shortest length
assert sol.stringIndices(
    ["abcd", "cd", "xyzcd"],
    ["cd"]
) == [1]

# Tie by earliest index
assert sol.stringIndices(
    ["aa", "bb", "cc"],
    ["dd"]
) == [0]

# Exact match preferred due to longest suffix
assert sol.stringIndices(
    ["abcd", "bcd", "cd"],
    ["abcd"]
) == [0]

# No suffix match at all
assert sol.stringIndices(
    ["hello", "world"],
    ["abc"]
) == [0]

# Multiple identical words
assert sol.stringIndices(
    ["test", "test", "test"],
    ["test"]
) == [0]

# Query longer than container words
assert sol.stringIndices(
    ["a", "ba", "cba"],
    ["zzzcba"]
) == [2]

# Deep Trie traversal
assert sol.stringIndices(
    ["abcdefghij"],
    ["fghij"]
) == [0]

print("All tests passed.")

Test Summary

Test	Why
Provided example 1	Validates standard suffix matching
Provided example 2	Validates longest suffix selection
Single word container	Simplest valid input
Tie by shortest length	Ensures primary tie breaker works
Tie by earliest index	Ensures secondary tie breaker works
Exact match	Validates longest suffix preference
No suffix match	Tests root fallback behavior
Multiple identical words	Ensures earliest index handling
Query longer than container	Validates traversal stopping correctly
Deep Trie traversal	Tests long matching paths

Edge Cases

No Common Suffix

A query may share absolutely no characters with any container word. This is a common source of bugs because Trie traversal immediately fails at the root.

For example:

wordsContainer = ["abc", "def"]
query = "xyz"

The correct answer is still a valid index. The longest common suffix is the empty string.

The implementation handles this by storing the globally best candidate directly at the root node. If traversal never progresses, the root's stored index is returned automatically.

Multiple Words With Same Length and Same Suffix

Consider:

wordsContainer = ["abc", "xbc"]
query = "bc"

Both words share suffix "bc" and both have equal length.

The problem requires choosing the earliest occurrence.

The implementation handles this inside is_better() by comparing indices whenever lengths are equal.

Query Longer Than Any Container Word

A query can be much longer than the matching container word:

wordsContainer = ["abc"]
query = "xyzabc"

The longest common suffix is still "abc".

Trie traversal naturally handles this because matching continues only while edges exist. Once the Trie path ends, traversal stops, and the deepest valid node already represents the longest available suffix match.