Count Prefix and Suffix Pairs II - Practice Coding Problems

Count Prefix and Suffix Pairs II - Problem

You are given a 0-indexed string array words.

Let's define a boolean function isPrefixAndSuffix that takes two strings, str1 and str2:

isPrefixAndSuffix(str1, str2) returns true if str1 is both a prefix and a suffix of str2, and false otherwise.

For example, isPrefixAndSuffix("aba", "ababa") is true because "aba" is a prefix of "ababa" and also a suffix, but isPrefixAndSuffix("abc", "abcd") is false.

Return an integer denoting the number of index pairs (i, j) such that i < j, and isPrefixAndSuffix(words[i], words[j]) is true.

Input & Output

Example 1 — Basic Case

$ Input: words = ["a","aba","ababa","aa"]

› Output: 4

💡 Note: Valid pairs: (0,1) "a" is prefix/suffix of "aba", (0,2) "a" is prefix/suffix of "ababa", (0,3) "a" is prefix/suffix of "aa", (1,2) "aba" is prefix/suffix of "ababa"

Example 2 — No Matches

$ Input: words = ["pa","papa","ma","mama"]

› Output: 2

💡 Note: Valid pairs: (0,1) "pa" is prefix/suffix of "papa", (2,3) "ma" is prefix/suffix of "mama"

Example 3 — Edge Case

$ Input: words = ["abab","ab"]

› Output: 0

💡 Note: No valid pairs since "abab" cannot be prefix/suffix of shorter "ab"

Constraints

1 ≤ words.length ≤ 5 × 10⁴
1 ≤ words[i].length ≤ 10⁵
words[i] consists only of lowercase English letters
The sum of lengths of all words[i] does not exceed 5 × 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input

Array of strings ["a", "aba", "ababa", "aa"]

Check Pairs

For each pair (i,j) where i < j, check prefix and suffix condition

Count Matches

Count pairs where words[i] is both prefix and suffix of words[j]

Key Takeaway

🎯 Key Insight: A string can only be both prefix and suffix if it appears at the beginning and end of another string

Asked in

G Google 15 f Facebook 12 a Amazon 8

The key insight is that we need to efficiently check if one string is both a prefix and suffix of another. The brute force approach checks all pairs in O(n² × m) time. Better approaches use Trie for prefix optimization or rolling hash for fast string comparison. Best approach depends on input characteristics: Trie for many common prefixes, rolling hash for fewer collisions. Time: O(n² × m), Space: O(n × m)

Common Approaches

Approach	Time	Space	Notes
✓ Trie-Based Optimization	O(n × m²)	O(n × m)	Use Trie data structure to efficiently find strings that share common prefixes and suffixes
Rolling Hash Optimization	O(n² + n × m)	O(n × m)	Use rolling hash to quickly compute and compare prefix/suffix hashes, avoiding full string comparisons
Brute Force	O(n² × m)	O(1)	Check every pair of strings (i,j) where i < j to see if words[i] is both prefix and suffix of words[j]

Trie-Based Optimization — Algorithm Steps

Build a Trie containing all strings
For each string, use Trie to find potential matches
Check if found strings have current string as both prefix and suffix
Count valid pairs

Visualization

Tap to expand

Step-by-Step Walkthrough

Build Trie

Insert all strings into Trie structure

Traverse for Prefix

For each string, find all with same prefix

Check Suffix

Among prefix matches, check suffix condition

Code -

solution.c — C

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

typedef struct TrieNode {
    struct TrieNode* children[26];
    int indices[1000];
    int indexCount;
} TrieNode;

TrieNode* createNode() {
    TrieNode* node = (TrieNode*)calloc(1, sizeof(TrieNode));
    node->indexCount = 0;
    return node;
}

int solution(char words[][101], int n) {
    if (n < 2) return 0;
    
    // Build trie
    TrieNode* root = createNode();
    for (int i = 0; i < n; i++) {
        TrieNode* node = root;
        for (int j = 0; words[i][j]; j++) {
            int idx = words[i][j] - 'a';
            if (!node->children[idx]) {
                node->children[idx] = createNode();
            }
            node = node->children[idx];
            node->indices[node->indexCount++] = i;
        }
    }
    
    int count = 0;
    for (int i = 0; i < n; i++) {
        // Find all strings that have words[i] as prefix
        TrieNode* node = root;
        int valid = 1;
        for (int j = 0; words[i][j]; j++) {
            int idx = words[i][j] - 'a';
            if (!node->children[idx]) {
                valid = 0;
                break;
            }
            node = node->children[idx];
        }
        
        if (valid) {
            // Check which also have words[i] as suffix
            for (int k = 0; k < node->indexCount; k++) {
                int j = node->indices[k];
                if (j > i) {
                    int len1 = strlen(words[i]);
                    int len2 = strlen(words[j]);
                    if (len2 >= len1 && strcmp(words[j] + len2 - len1, words[i]) == 0) {
                        count++;
                    }
                }
            }
        }
    }
    
    return count;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    char words[1000][101];
    int n = 0;
    
    char* token = strtok(line, "[]");
    token = strtok(NULL, "\"");
    
    while (token != NULL) {
        if (strlen(token) > 0 && token[0] != ',' && token[0] != ' ') {
            strcpy(words[n], token);
            n++;
        }
        token = strtok(NULL, "\"");
    }
    
    int result = solution(words, n);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × m²)

Building Trie takes O(n×m), checking each string against others takes O(n×m²) where n is number of strings, m is average length

✓ Linear Growth

Space Complexity

O(n × m)

Trie stores all strings, worst case O(n×m) space for nodes

⚡ Linearithmic Space

2.5K Views

Medium Frequency

~35 min Avg. Time

89 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

Trie-Based Optimization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler