# Count Prefix and Suffix Pairs I
**Difficulty:** EASY
[External](https://leetcode.com/problems/count-prefix-and-suffix-pairs-i)
Canonical: https://scaleengineer.com/dsa/problems/count-prefix-and-suffix-pairs-i
**Patterns:** [String Matching](https://scaleengineer.com/dsa/patterns/string-matching), [Rolling Hash](https://scaleengineer.com/dsa/patterns/rolling-hash), [Hash Function](https://scaleengineer.com/dsa/patterns/hash-function)
**Data structures:** Array, String, Trie
**Companies:** [Capital One](https://scaleengineer.com/companies/capital-one), [Autodesk](https://scaleengineer.com/companies/autodesk)
---
## 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`_._

**Example 1:**

**Input:** words = ["a","aba","ababa","aa"]
**Output:** 4
**Explanation:** 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
**Explanation:** 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
**Explanation:** 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.

# Approaches
## Brute-Force Iteration
The most straightforward approach is to iterate through all possible pairs of indices `(i, j)` where `i < j` and check if `words[i]` is both a prefix and a suffix of `words[j]`. This involves nested loops and direct string comparisons.
**Time:** O(N^2 * L), where `N` is the number of words and `L` is the maximum length of a word. We have two nested loops giving `O(N^2)` pairs. For each pair, `startsWith` and `endsWith` operations take up to `O(L)` time. · **Space:** O(1), as we only use a constant amount of extra space for the counter and loop variables.
**Pros:** Simple to understand and implement.; Very low memory usage.; Sufficiently fast for the given problem constraints.
**Cons:** Less efficient than other possible solutions. The time complexity is quadratic in the number of words, which would be too slow for larger inputs.
### Explanation
We initialize a counter variable `count` to zero. We use two nested loops to generate all unique pairs of indices `(i, j)` such that `i` is less than `j`. The outer loop runs from `i = 0` to `words.length - 1`, and the inner loop runs from `j = i + 1` to `words.length - 1`. Inside the inner loop, for each pair of strings `words[i]` and `words[j]`, we perform the required check. A simple optimization is to first check if the length of `words[i]` is greater than the length of `words[j]`. If it is, `words[i]` cannot be a prefix or suffix, so we can skip to the next pair. We then use built-in string functions to check the conditions. `words[j].startsWith(words[i])` checks for the prefix condition, and `words[j].endsWith(words[i])` checks for the suffix condition. If both functions return `true`, it means we have found a valid pair, so we increment our `count`. After the loops complete, `count` holds the total number of such pairs.

```java
class Solution {
    public int countPrefixAndSuffixPairs(String[] words) {
        int count = 0;
        int n = words.length;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                String str1 = words[i];
                String str2 = words[j];
                if (str2.startsWith(str1) && str2.endsWith(str1)) {
                    count++;
                }
            }
        }
        return count;
    }
}
```
### Algorithm
- Initialize a counter variable `count` to zero.
- Use two nested loops to generate all unique pairs of indices `(i, j)` such that `i < j`. The outer loop runs from `i = 0` to `words.length - 1`, and the inner loop runs from `j = i + 1` to `words.length - 1`.
- Inside the inner loop, for each pair of strings `words[i]` and `words[j]`, perform the required check.
- Use built-in string functions to check the conditions: `words[j].startsWith(words[i])` for the prefix condition and `words[j].endsWith(words[i])` for the suffix condition.
- If both functions return `true`, it means we have found a valid pair, so we increment our `count`.
- After the loops complete, `count` holds the total number of such pairs, which is then returned.

## Optimized Approach using a Hash Map
A more optimized approach involves iterating through the words array once. For each word, we find all of its prefixes that are also suffixes. Then, we use a hash map to efficiently look up how many times these special "prefix-suffix" strings have appeared as complete words earlier in the array.
**Time:** O(N * L^2), where `N` is the number of words and `L` is the maximum length of a word. The outer loop runs `N` times. The inner loop runs `L` times. Inside the inner loop, `substring`, `endsWith`, and `getOrDefault` (with string hashing) each take `O(L)` time in the worst case. This results in `N * L * L = O(N * L^2)`. · **Space:** O(N * L), where `N` is the number of words and `L` is the maximum length of a word. In the worst case, all words are unique and the hash map will store all of them, consuming space proportional to the total number of characters in the input.
**Pros:** More efficient time complexity compared to the brute-force approach, especially for larger `N`.; Processes the array in a single pass.
**Cons:** Uses extra space to store word frequencies, unlike the `O(1)` space brute-force method.; Slightly more complex to implement due to the use of a hash map and prefix generation logic.
### Explanation
This method avoids the `O(N^2)` pair-wise comparison by processing the array in a single pass. We maintain a hash map to store the frequency of words encountered so far. We initialize a counter `count` to zero and a `HashMap<String, Integer>` to store word frequencies. We iterate through each `word` in the `words` array. For each `word`, we need to find how many previously seen words are a prefix-and-suffix of the current `word`. To do this, we iterate through all possible prefixes of the current `word`. For each `prefix`, we check if it's also a suffix of the `word`. If a `prefix` is also a suffix, we look it up in our frequency map. If it exists, we add its stored frequency to our total `count`. This is because every previous occurrence of that string forms a valid pair with the current `word`. After checking all prefixes for the current `word`, we update the frequency map with the current `word` itself, incrementing its count or adding it if it's the first time we've seen it. This makes it available for subsequent words in the array.

```java
import java.util.HashMap;
import java.util.Map;

class Solution {
    public int countPrefixAndSuffixPairs(String[] words) {
        int count = 0;
        // This map will store the frequency of each word encountered so far.
        Map<String, Integer> freq = new HashMap<>();

        for (String word : words) {
            // For the current word, check all its prefixes.
            for (int k = 1; k <= word.length(); k++) {
                String prefix = word.substring(0, k);
                // Check if the prefix is also a suffix.
                if (word.endsWith(prefix)) {
                    // If this prefix has been seen before as a full word,
                    // it forms a valid pair with the current word.
                    // Add the number of times it has appeared to the count.
                    count += freq.getOrDefault(prefix, 0);
                }
            }
            // Update the frequency map with the current word.
            freq.put(word, freq.getOrDefault(word, 0) + 1);
        }
        return count;
    }
}
```
### Algorithm
- Initialize `count = 0`.
- Initialize an empty `HashMap<String, Integer>` called `freq` to store the frequency of words seen so far.
- Iterate through each `word` in the `words` array.
- For the current `word`, iterate through its possible prefix lengths `k` from `1` to `word.length()`.
- Get the prefix `p` of length `k`.
- Check if `word` also ends with `p`.
- If it does, look up `p` in the `freq` map. Add the frequency of `p` (or 0 if not present) to `count`.
- After checking all prefixes for the current `word`, update its frequency in the `freq` map.
- After iterating through all words, return `count`.

# Solutions
### Java

```java
class Solution {
public
  int countPrefixSuffixPairs(String[] words) {
    int ans = 0;
    int n = words.length;
    for (int i = 0; i < n; ++i) {
      String s = words[i];
      for (int j = i + 1; j < n; ++j) {
        String t = words[j];
        if (t.startsWith(s) && t.endsWith(s)) {
          ++ans;
        }
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int countPrefixSuffixPairs(vector<string> &words) {
    int ans = 0;
    int n = words.size();
    for (int i = 0; i < n; ++i) {
      string s = words[i];
      for (int j = i + 1; j < n; ++j) {
        string t = words[j];
        if (t.find(s) == 0 && t.rfind(s) == t.length() - s.length()) {
          ++ans;
        }
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def countPrefixSuffixPairs(self, words: List[str]) -> int: ans = 0 for i, s in enumerate(words): for t in words[i + 1:]: ans += t . endswith(s) and t . startswith(s) return ans

```