How to Solve Count Prefix and Suffix Pairs I

This problem requires counting pairs of indices (i, j) where words[i] is both a prefix and suffix of words[j]. Iterate through all index combinations and apply a direct string check for each pair. The solution balances simplicity and performance using nested loops and optional hash-based optimizations for repeated strings.

Problem Statement

Given a 0-indexed array of strings words, find the total number of pairs of indices (i, j) where i != j and words[i] is both a prefix and a suffix of words[j]. Define isPrefixAndSuffix(str1, str2) to return true if str1 is a prefix and a suffix of str2.

For example, if words = ["a","aba","ababa","aa"], the pairs that satisfy isPrefixAndSuffix are counted by checking each combination. Return the total count as an integer. Constraints: 1 <= words.length <= 50, 1 <= words[i].length <= 10, and words[i] contains only lowercase letters.

Examples

Example 1

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

Output: 4

In this example, the counted index pairs are: i = 0 and j = 1 because isPrefixAndSuffix("a", "aba") is true. i = 0 and j = 2 because isPrefixAndSuffix("a", "ababa") is true. i = 0 and j = 3 because isPrefixAndSuffix("a", "aa") is true. i = 1 and j = 2 because isPrefixAndSuffix("aba", "ababa") is true. Therefore, the answer is 4.

Example 2

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

Output: 2

In this example, the counted index pairs are: i = 0 and j = 1 because isPrefixAndSuffix("pa", "papa") is true. i = 2 and j = 3 because isPrefixAndSuffix("ma", "mama") is true. Therefore, the answer is 2.

Example 3

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

Output: 0

In this example, the only valid index pair is i = 0 and j = 1, and isPrefixAndSuffix("abab", "ab") is false. Therefore, the answer is 0.

Constraints

• 1 <= words.length <= 50
• 1 <= words[i].length <= 10
• words[i] consists only of lowercase English letters.

Solution Approach

Naive Double Loop Check

Iterate over all index pairs (i, j) with i != j, and for each pair, check if words[i] is both a prefix and suffix of words[j] using simple string comparison. Increment a counter for each valid pair. This approach is direct and works well due to small input size.

Optimized String Matching

Use rolling hash or direct substring comparison to check the prefix and suffix conditions efficiently. Precompute string hashes if needed to avoid repeated slicing. This reduces the overhead when words have repeated patterns and leverages the array plus string pattern.

Trie-Based Prefix-Suffix Lookup

Build a trie storing all words for fast prefix checking and reverse trie for suffix checking. For each word, query both tries to find potential matches quickly. This method reduces redundant checks and highlights the pattern of combining array iteration with string matching structures.

Complexity Analysis

Time complexity is O(n^2 * m) because each of the n words is compared with every other word, and checking prefix and suffix takes O(m) time where m is the word length. Space complexity is O(n * m) for storing precomputed hashes or trie nodes.

What Interviewers Usually Probe

• Mentions combining array iteration with string checks for prefix and suffix patterns.
• Asks how to handle repeated strings efficiently in nested loops.
• Looks for solutions that can leverage string structures like trie or hash maps.

Common Pitfalls or Variants

Common pitfalls

• Forgetting to exclude pairs where i equals j.
• Checking only prefix or only suffix instead of both simultaneously.
• Not accounting for overlapping prefixes and suffixes correctly when strings are identical or nested.

Follow-up variants

• Count prefix-suffix pairs with variable-length substring matching instead of full word.
• Extend to allow wildcards in prefix or suffix for pattern matching.
• Find all pairs in larger arrays efficiently using rolling hash or trie optimizations.

How GhostInterview Helps

• Highlights index pair iteration with direct isPrefixAndSuffix checks to save time during coding.
• Provides structured approaches like hash or trie optimizations to reduce repeated comparisons.
• Clarifies the array plus string pattern and offers step-by-step reasoning for counting valid pairs.

Topic Pages

• Array
• String
• Trie
• Rolling Hash
• String Matching
• Hash Function

Related GhostInterview Pages

• LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
• Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
• How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.

FAQ

What is the core idea behind Count Prefix and Suffix Pairs I?

The core idea is to iterate over all pairs of words and count those where one word is both a prefix and a suffix of the other, leveraging array plus string techniques.

Can we use a hash map to optimize this problem?

Yes, using a hash map to store precomputed prefixes or suffixes allows faster repeated lookups and reduces redundant string comparisons.

Is a trie necessary to solve this problem?

No, a trie is optional. Nested loops with direct string checks are sufficient for small arrays, but a trie can improve efficiency for larger inputs.

What is the time complexity for checking all prefix-suffix pairs?

The time complexity is O(n^2 * m), where n is the number of words and m is the maximum word length, due to nested comparisons and string checks.

How does the array plus string pattern influence the solution?

It guides using array iteration to traverse index pairs while applying string operations like prefix and suffix checks, which is the central strategy for this problem.