Longest Common Suffix Queries - Practice Coding Problems

Longest Common Suffix Queries - Problem

You are given two arrays of strings wordsContainer and wordsQuery. For each wordsQuery[i], you need to find a string from wordsContainer that has the longest common suffix with wordsQuery[i].

If there are two or more strings in wordsContainer that share the longest common suffix, find the string that is the smallest in length. If there are two or more such strings that have the same smallest length, find the one that occurred earlier in wordsContainer.

Return an array of integers ans, where ans[i] is the index of the string in wordsContainer that has the longest common suffix with wordsQuery[i].

Input & Output

Example 1 — Basic Case

$ Input: wordsContainer = ["ababa","ba","aba"], wordsQuery = ["aba"]

› Output: [2]

💡 Note: Query 'aba' has longest common suffix 'aba' with wordsContainer[0] and wordsContainer[2]. Since wordsContainer[2] is shorter (length 3 vs 5), return index 2.

Example 2 — Earlier Index Priority

$ Input: wordsContainer = ["abc","bcd","def"], wordsQuery = ["xyz"]

› Output: [0]

💡 Note: Query 'xyz' has no common suffix with any container word (all return suffix length 0). Since all have same suffix length, choose the earliest index 0.

Example 3 — Multiple Queries

$ Input: wordsContainer = ["a","aa","aaa"], wordsQuery = ["aa","a"]

› Output: [0,0]

💡 Note: Query 'aa': suffix 'a' matches all, choose shortest word at index 0. Query 'a': suffix 'a' matches all, choose shortest word at index 0.

Constraints

1 ≤ wordsContainer.length, wordsQuery.length ≤ 10⁴
1 ≤ wordsContainer[i].length ≤ 5 × 10³
1 ≤ wordsQuery[i].length ≤ 5 × 10³
wordsContainer[i] consists only of lowercase English letters
wordsQuery[i] consists only of lowercase English letters

Visualization

Tap to expand

Understanding the Visualization

Input

Container words and query words

Process

Find longest common suffix with priority rules

Output

Index of best matching container word for each query

Key Takeaway

🎯 Key Insight: Build suffix trie to efficiently find longest common suffixes with O(k) query time

Asked in

G Google 25 a Amazon 18 M Microsoft 15

The key insight is to use suffix matching with priority rules. The optimal approach uses a suffix trie to precompute the best match for each possible suffix, enabling O(k) query time where k is the query length. Time: O(S + Q×k), Space: O(S×26) where S is total character count.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Comparison	O(n × m × k)	O(1)	Compare each query word with every container word to find longest common suffix
Suffix Trie with Metadata	O(S + Q × k)	O(S × 26)	Build a suffix trie storing best match info at each node for instant lookup

Brute Force Comparison — Algorithm Steps

For each query word, examine all container words
Compare characters from end to start to find common suffix length
Track best match considering suffix length, word length, and index order

Visualization

Tap to expand

Step-by-Step Walkthrough

Start

Take first query word

Compare

Check suffix match with each container word

Result

Return index of best match

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int commonSuffixLength(const char* s1, const char* s2) {
    int len1 = strlen(s1), len2 = strlen(s2);
    int i = len1 - 1, j = len2 - 1;
    int length = 0;
    while (i >= 0 && j >= 0 && s1[i] == s2[j]) {
        length++;
        i--;
        j--;
    }
    return length;
}

int* solution(char wordsContainer[][51], int containerSize, char wordsQuery[][51], int querySize, int* returnSize) {
    *returnSize = querySize;
    int* result = (int*)malloc(querySize * sizeof(int));
    
    for (int q = 0; q < querySize; q++) {
        int bestIdx = 0;
        int bestSuffixLen = commonSuffixLength(wordsContainer[0], wordsQuery[q]);
        int bestWordLen = strlen(wordsContainer[0]);
        
        for (int i = 1; i < containerSize; i++) {
            int suffixLen = commonSuffixLength(wordsContainer[i], wordsQuery[q]);
            int wordLen = strlen(wordsContainer[i]);
            
            if (suffixLen > bestSuffixLen || 
                (suffixLen == bestSuffixLen && wordLen < bestWordLen)) {
                bestIdx = i;
                bestSuffixLen = suffixLen;
                bestWordLen = wordLen;
            }
        }
        
        result[q] = bestIdx;
    }
    return result;
}

int main() {
    char wordsContainer[1000][51], wordsQuery[1000][51];
    int containerSize = 0, querySize = 0;
    
    // Simple parsing - read arrays manually
    scanf("%d", &containerSize);
    for (int i = 0; i < containerSize; i++) {
        scanf("%s", wordsContainer[i]);
    }
    scanf("%d", &querySize);
    for (int i = 0; i < querySize; i++) {
        scanf("%s", wordsQuery[i]);
    }
    
    int returnSize;
    int* result = solution(wordsContainer, containerSize, wordsQuery, querySize, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × m × k)

n queries × m container words × k average word length for suffix comparison

✓ Linear Growth

Space Complexity

O(1)

Only using variables for tracking, no extra data structures

✓ Linear Space

33.8K Views

Medium Frequency

~35 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Comparison — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler