Longest Common Suffix Queries

Dec 18, 2024 • 6 mins read

Dhaval Trivedi

Co-founder, Airtribe

Problem Overview

In the problem "Longest Common Suffix Queries" (as referenced on LeetCode), we are asked to work with strings and queries to discover the longest common suffix shared between them. This problem requires efficient handling of string manipulations, making it an ideal candidate for a Trie (prefix tree) data structure, albeit a twist with suffixes.

Understanding the Problem

Given a list of words and a series of queries, each consisting of a pair of indices (i, j), our task is to determine the longest common suffix of the words at these indices. A common suffix is the longest substring present at the end of both words that aligns perfectly in reverse.

Example

Suppose we are given:

Words list: ["resignation", "nation", "destination"]
Queries: [(0, 1), (1, 2)]

For query (0, 1), the longest common suffix between "resignation" and "nation" is "nation", while for query (1, 2), it is "tion".

Key DSA Concepts and Theory

Trie (Prefix Tree)

A Trie is a specialized tree used to store associative data structures. In particular, it is efficient for dynamic set or associative array-like applications, which have keys that are usually strings.

Usage in this problem:

Normally, Tries are used to manage prefixes, but they can be adapted for suffixes by inserting reversed words.
The key operation here is to determine the length of the longest common suffix, which can be efficiently discovered using a reversed Trie.

String Manipulation

String manipulation in the context of this problem involves:

Reversing strings for insertion into the Trie.
Comparing strings based on characters from the end toward the start.

Solution Approach

Step-by-Step Solution

Reverse the Words: Since a Trie typically handles prefixes, reverse each word in the list of words. This adaptation allows us to use prefix logic to solve a suffix problem.
Build a Suffix Trie: Create a Trie where each node represents a character of the newly reversed words. Insert each reversed word into the Trie.
Process Queries: For each query (i, j), search in the Trie to find the longest common prefix (which corresponds to the longest common suffix since words are reversed) of the reversed words at indices i and j.
Retrieve Results: For each query, retrieve and store the result of the longest common suffix length.
Return Results: Return the results for all queries in a list format.

Code Examples

C++ Implementation

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

class TrieNode {
public:
    TrieNode* children[26];
    TrieNode() {
        for (int i = 0; i < 26; ++i) {
            children[i] = nullptr;
        }
    }
};

class Trie {
public:
    TrieNode* root;
    Trie() {
        root = new TrieNode();
    }
    
    void insert(const std::string& word) {
        TrieNode* node = root;
        for (char c : word) {
            int index = c - 'a';
            if (!node->children[index]) {
                node->children[index] = new TrieNode();
            }
            node = node->children[index];
        }
    }
    
    int longestCommonPrefix(const std::string& word1, const std::string& word2) {
        TrieNode* node = root;
        int length = 0;
        for (int i = 0; i < std::min(word1.length(), word2.length()); ++i) {
            int index1 = word1[i] - 'a';
            int index2 = word2[i] - 'a';
            if (index1 == index2 && node->children[index1]) {
                node = node->children[index1];
                ++length;
            } else {
                break;
            }
        }
        return length;
    }
};

std::vector<int> longestCommonSuffixQueries(const std::vector<std::string>& words, const std::vector<std::pair<int, int>>& queries) {
    Trie trie;
    std::vector<std::string> reversedWords = words;
    for (auto& word : reversedWords) {
        std::reverse(word.begin(), word.end());
        trie.insert(word);
    }
    
    std::vector<int> results;
    for (const auto& query : queries) {
        std::string& word1 = reversedWords[query.first];
        std::string& word2 = reversedWords[query.second];
        int length = trie.longestCommonPrefix(word1, word2);
        results.push_back(length);
    }
    return results;
}

int main() {
    std::vector<std::string> words = {"resignation", "nation", "destination"};
    std::vector<std::pair<int, int>> queries = {{0, 1}, {1, 2}};
    std::vector<int> results = longestCommonSuffixQueries(words, queries);
    
    for (int result : results) {
        std::cout << result << std::endl;
    }
    return 0;
}

Java Implementation

import java.util.*;

class TrieNode {
    TrieNode[] children;
    TrieNode() {
        children = new TrieNode[26];
    }
}

class Trie {
    TrieNode root;
    Trie() {
        root = new TrieNode();
    }

    void insert(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            int index = c - 'a';
            if (node.children[index] == null) {
                node.children[index] = new TrieNode();
            }
            node = node.children[index];
        }
    }

    int longestCommonPrefix(String word1, String word2) {
        TrieNode node = root;
        int length = 0;
        for (int i = 0; i < Math.min(word1.length(), word2.length()); i++) {
            int index1 = word1.charAt(i) - 'a';
            int index2 = word2.charAt(i) - 'a';
            if (index1 == index2 && node.children[index1] != null) {
                node = node.children[index1];
                length++;
            } else {
                break;
            }
        }
        return length;
    }
}

public class Solution {
    public static List<Integer> longestCommonSuffixQueries(List<String> words, List<int[]> queries) {
        Trie trie = new Trie();
        List<String> reversedWords = new ArrayList<>(words);
        for (int i = 0; i < reversedWords.size(); i++) {
            String reversed = new StringBuilder(reversedWords.get(i)).reverse().toString();
            reversedWords.set(i, reversed);
            trie.insert(reversed);
        }

        List<Integer> results = new ArrayList<>();
        for (int[] query : queries) {
            String word1 = reversedWords.get(query[0]);
            String word2 = reversedWords.get(query[1]);
            int length = trie.longestCommonPrefix(word1, word2);
            results.add(length);
        }
        return results;
    }

    public static void main(String[] args) {
        List<String> words = Arrays.asList("resignation", "nation", "destination");
        List<int[]> queries = Arrays.asList(new int[]{0, 1}, new int[]{1, 2});
        List<Integer> results = longestCommonSuffixQueries(words, queries);

        for (int result : results) {
            System.out.println(result);
        }
    }
}

Time and Space Complexity Analysis

Time Complexity:
- Building the Trie: O(N * L), where N is the number of words and L is the average length of the word (assuming maximum word length is constant).
- Processing each query: O(L)
- Total complexity for Q queries is O(Q * L).
Space Complexity:
- Trie Storage: O(T), where T represents the total number of nodes created, which in worst-case is proportional to the sum of all characters in all words, i.e., O(N * L).

Common Mistakes to Avoid

Forgetting to reverse the strings before insertion into the Trie might lead you to solve an entirely different problem.
Ensure character indices are correctly configured for TrieNode children arrays, as this could lead to ArrayIndexOutOfBounds exceptions.

Additional Resources and References

This comprehensive guide provides an understanding of solving the "Longest Common Suffix Queries" using Trie, complete with code examples in C++ and Java, and an analysis of time and space complexities.