#3093

Hard

LeetCode Problem Workspace

Longest Common Suffix Queries

Find the index of the string in wordsContainer with the longest common suffix for each query efficiently using array and string patterns.

array string trie

Problem Statement

You are given two arrays of lowercase strings: wordsContainer and wordsQuery. For each string in wordsQuery, determine the string from wordsContainer that shares the longest common suffix with it. If multiple strings tie on suffix length, choose the one with the smallest length. If a tie still exists, select the string that appears earliest in wordsContainer.

Return an array ans of integers where ans[i] represents the index of the selected string in wordsContainer corresponding to wordsQuery[i]. Efficient suffix matching and proper tie-breaking are crucial due to large array sizes and string lengths.

Examples

Example 1

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

Output: [1,1,1]

Let's look at each wordsQuery[i] separately:

Example 2

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

Output: [2,0,2]

Let's look at each wordsQuery[i] separately:

Constraints

1 <= wordsContainer.length, wordsQuery.length <= 104
1 <= wordsContainer[i].length <= 5 * 103
1 <= wordsQuery[i].length <= 5 * 103
wordsContainer[i] consists only of lowercase English letters.
wordsQuery[i] consists only of lowercase English letters.
Sum of wordsContainer[i].length is at most 5 * 105.
Sum of wordsQuery[i].length is at most 5 * 105.

Solution Approach

Reverse strings and build a trie

Reverse all strings in wordsContainer and wordsQuery. Insert reversed wordsContainer strings into a trie with nodes tracking index and original length. This converts the suffix problem into a prefix problem, allowing quick traversal for each reversed query.

Query trie for longest matching prefix

For each reversed query string, traverse the trie to find the deepest node that matches the prefix. Track all candidates with maximum prefix length, then select the one with the smallest length and earliest index to satisfy tie-breaking rules.

Construct answer array

Map the selected trie nodes back to original wordsContainer indices to fill ans array. This approach ensures O(total characters) time complexity if using an efficient trie implementation and avoids redundant suffix comparisons.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity depends on total characters in wordsContainer and wordsQuery for building and traversing the trie, roughly O(sum of lengths). Space complexity is also O(sum of lengths) for the trie structure.

What Interviewers Usually Probe

You are reversing strings to simplify the suffix problem.
You need to track multiple tie-breaking rules: length and index.
Efficient matching requires a trie or hashmap, naive comparisons will timeout.

Common Pitfalls or Variants

Common pitfalls

Ignoring tie-breaker rules can yield incorrect indices.
Using naive suffix comparison for every query causes timeouts.
Forgetting to reverse strings before building the trie changes logic.

Follow-up variants

Find longest common suffix with at most k mismatches.
Return the actual matching string instead of index.
Handle dynamic insertion and deletion in wordsContainer.

FAQ

What is the main trick to solve Longest Common Suffix Queries?

Reverse all strings to transform the suffix problem into a prefix problem, then use a trie for efficient matching.

How do I handle ties in suffix length?

Select the string with the smallest length; if still tied, pick the earliest occurrence in wordsContainer.

Can I use brute force for this problem?

Brute force is too slow for large arrays; reversing strings and using a trie is necessary for efficiency.

Why does reversing strings help?

Reversing converts suffix matching into prefix matching, which is easier to implement and optimize using a trie.

What data structures are best for this pattern?

Tries or hash maps are ideal to track reversed strings and efficiently retrieve longest matching prefixes.

terminal

Solution

Solution 1: Trie

The problem requires us to find the longest common suffix, so we can consider using a Trie.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

class Trie:
    __slots__ = ("children", "length", "idx")

    def __init__(self):
        self.children = [None] * 26
        self.length = inf
        self.idx = inf

    def insert(self, w: str, i: int):
        node = self
        if node.length > len(w):
            node.length = len(w)
            node.idx = i
        for c in w[::-1]:
            idx = ord(c) - ord("a")
            if node.children[idx] is None:
                node.children[idx] = Trie()
            node = node.children[idx]
            if node.length > len(w):
                node.length = len(w)
                node.idx = i

    def query(self, w: str) -> int:
        node = self
        for c in w[::-1]:
            idx = ord(c) - ord("a")
            if node.children[idx] is None:
                break
            node = node.children[idx]
        return node.idx


class Solution:
    def stringIndices(
        self, wordsContainer: List[str], wordsQuery: List[str]
    ) -> List[int]:
        trie = Trie()
        for i, w in enumerate(wordsContainer):
            trie.insert(w, i)
        return [trie.query(w) for w in wordsQuery]

Continue Practicing

#3076 shortest uncommon substring in an array #3045 count prefix and suffix pairs ii #3043 find the length of the longest common prefix