3042. Count Prefix and Suffix Pairs I

EasyTrieArrayStringString MatchingHash FunctionRolling Hash
Leetcode Link

Problem Description

In this problem, we're given an array of 0-indexed strings and we need to count the number of pairs of indices (i, j) for which the string at index i is both a prefix and a suffix of the string at index j, and i must be less than j. A prefix of a string is a leading substring of the original string, while a suffix is a trailing substring.

For clarity, let's consider what constitutes a prefix and a suffix:

  • A prefix of a string is the start of that string. For example, "cat" is a prefix of "cater".
  • A suffix is the end of the string. For example, "ter" is a suffix of "cater".

Therefore, if a given string is both a prefix and a suffix of another, it appears at both the beginning and the end of the other string. The function isPrefixAndSuffix(str1, str2) is supposed to return true if str1 is both a prefix and suffix of str2, otherwise false.

The task is to count how many such distinct index pairs (i, j) exist in the given array where i < j.

Intuition

To solve this problem, we need to look at every possible pair of strings where the first string could be a potential prefix and suffix for the second string. We can do this through a nested loop where we iterate over each string and compare it with every other string that comes after it in the array.

When comparing the strings, we use two important string operations: startswith() and endswith(). These methods return true if the first string is a prefix or suffix of the second string, respectively:

  1. The method startswith(s) will check if the string under consideration starts with the substring s.
  2. Likewise, endswith(s) will verify if the string ends with the substring s.

By ensuring that both these conditions are true for a pair of strings, we confirm that the first string is both a prefix and a suffix of the second one.

We only consider pairs where the first string index is less than the second (i < j), to comply with the problem statement. For each such valid pair, we increment our answer. This ensures that we count all the unique pairs that satisfy the condition. The summed total gives us the desired output.

Learn more about Trie patterns.

Solution Approach

The implementation of the solution utilizes a straightforward brute force approach, where we simply iterate through every possible pair of strings and check if one string is both a prefix and a suffix of the other.

The algorithm can be described as follows:

  1. Initialize a counter (let's call it ans) and set it to 0. This will hold the count of valid pairs (i, j) we find.
  2. Use nested loops to iterate through the array of strings:
    • The outer loop will go through each string s in the array, starting from the first element up to the second-to-last. We use enumerate to get the index i alongside the string s.
    • The inner loop will iterate through the remaining elements in the array, starting from the index i + 1 and continuing to the end of the array. These will be the strings t against which we will compare s.
  3. For each pair of strings (s, t), where s is from the outer loop and t is from the inner loop:
    • We check if string t starts with s using t.startswith(s).
    • Simultaneously, we check if string t ends with s using t.endswith(s).
    • If both conditions are true, meaning s is both a prefix and suffix of t, increment ans by 1.
  4. After the loops complete, return the count ans which now contains the number of index pairs (i, j) where isPrefixAndSuffix(words[i], words[j]) is true.

There are no advanced data structures utilized in this solution; it's a simple application of nested iteration over the given array and string comparison methods. The efficiency of the algorithm is not optimized; it operates with a time complexity of O(n^2 * m) where n is the length of the words array, and m is the average string length. This is because for every pair of strings, we potentially check each character up to the length of the shorter string twice (once for prefix, once for suffix).

Even though the solution is not the most optimal, it works well for small datasets and serves as a clear example of how to implement such a count conditionally on a collection of strings.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What is the worst case running time for finding an element in a binary search tree(not necessarily balanced) of size n?

Example Walkthrough

Let's consider a simple example to illustrate the solution approach. Suppose we are given the following array of strings:

1words = ["one", "oneon", "neon", "oneonne"]

We want to find the count of pairs of indices (i, j) such that the string at index i is both a prefix and a suffix of the string at index j, with i < j.

Here's how we apply the solution step by step:

  1. Initialize ans to 0.
  2. Iterate over the array to consider every potential string s:
    • At i = 0, s = "one".
      • Now we compare s with every other string t with index greater than i.
      • At j = 1, t = "oneon". We find that t.startswith(s) is True but t.endswith(s) is False. Since both conditions are not met, we do not increment ans.
      • At j = 2, t = "neon". Neither t.startswith(s) nor t.endswith(s) are True, so we continue.
      • At j = 3, t = "oneonne". Both t.startswith(s) and t.endswith(s) are True. So, we increment ans by 1. Now, ans = 1.
    • Move to i = 1, s = "oneon". Repeat the steps, but there are no strings after s that satisfy the conditions.
    • Continue to i = 2, s = "neon". There's only one string after this, and it doesn't satisfy the conditions.
  3. No further pairs can be considered because i should be less than j, and we have exhausted all possibilities.
  4. Finally, return the count ans, which in this case is 1.

Therefore, there is only 1 valid pair (0, 3) where the first string is both a prefix and a suffix of the second string, and i is less than j.

Solution Implementation

1from typing import List
2
3class Solution:
4    def count_prefix_suffix_pairs(self, words: List[str]) -> int:
5        # Initialize a variable to count the pairs
6        pair_count = 0
7      
8        # Iterate through each word in the list
9        for i, source_word in enumerate(words):
10            # Compare with every other word in the list that comes after the current word
11            for target_word in words[i + 1:]:
12                # Increase the count if target_word starts and ends with source_word
13                pair_count += target_word.endswith(source_word) and target_word.startswith(source_word)
14      
15        # Return the total count of pairs
16        return pair_count
17
1class Solution {
2    // Method to count the number of pairs where one word is both a prefix and a suffix of another word.
3    public int countPrefixSuffixPairs(String[] words) {
4        int pairCount = 0; // Initialize counter for pairs to 0.
5        int wordCount = words.length; // Store the length of the words array.
6      
7        // Iterate over all words in the array using two nested loops to consider pairs.
8        for (int i = 0; i < wordCount; ++i) {
9            String currentWord = words[i]; // The current word for prefix/suffix checking
10          
11            // Iterate over the words following the current word to avoid duplicate pairs.
12            for (int j = i + 1; j < wordCount; ++j) {
13                String comparisonWord = words[j]; // Word to compare with the current word
14              
15                // Check if the comparison word starts with and ends with the current word.
16                if (comparisonWord.startsWith(currentWord) && comparisonWord.endsWith(currentWord)) {
17                    pairCount++; // Increment the number of valid pairs if conditions are met.
18                }
19            }
20        }
21      
22        return pairCount; // Return the final count of valid pairs.
23    }
24}
25
1class Solution {
2public:
3    // Function to count the number of pairs of strings in the given vector 'words'
4    // where one string is a prefix as well as a suffix of the other string.
5    int countPrefixSuffixPairs(vector<string>& words) {
6        int count = 0;                     // Initialize the count of valid pairs
7        int numWords = words.size();       // Get the number of words in the vector
8        // Iterate over each word in the vector as the potential prefix/suffix
9        for (int i = 0; i < numWords; ++i) {
10            string prefixSuffix = words[i];      
11            // Iterate over the remaining words in the vector to find a match
12            for (int j = i + 1; j < numWords; ++j) {
13                string candidate = words[j]; 
14                // Check that the word at index i is a prefix of the word at index j
15                if (candidate.find(prefixSuffix) == 0 &&
16                    // Additionally check that it is also a suffix of the word at index j
17                    candidate.rfind(prefixSuffix) == candidate.length() - prefixSuffix.length()) {
18                    count++;    // If both prefix and suffix conditions are satisfied, increment count
19                }
20            }
21        }
22        return count; // Return the total count of valid prefix and suffix pairs
23    }
24};
25
1// Counts the number of pairs where one string in the array is both a prefix and a suffix of another string.
2// @param {string[]} words - An array of words to check for prefix-suffix pairs.
3// @returns {number} The count of prefix-suffix pairs found in the array.
4function countPrefixSuffixPairs(words: string[]): number {
5    // Initialize a variable to keep track of the count of pairs.
6    let pairCount = 0;
7  
8    // Loop through each word in the array.
9    for (let i = 0; i < words.length; ++i) {
10        const word = words[i];
11      
12        // Loop through the remaining words in the array starting from the next index.
13        for (const otherWord of words.slice(i + 1)) {
14            // Check if the current word is both a prefix and a suffix of the other word.
15            if (otherWord.startsWith(word) && otherWord.endsWith(word)) {
16                // Increment the count of pairs if the condition is met.
17                ++pairCount;
18            }
19        }
20    }
21  
22    // Return the total count of prefix-suffix pairs.
23    return pairCount;
24}
25

Time and Space Complexity

Time Complexity

The provided function iterates over each word using a nested loop structure. The outer loop runs n times where n is the length of the words list. For each iteration of the outer loop, the inner loop runs n - i - 1 times, where i is the current index of the outer loop. There, each comparison between two strings, for startswith and endswith, can take up to m operations where m is the maximum length of the strings in the words list. Hence, the worst-case time complexity is O(n^2 * m).

Space Complexity

The function mainly uses constant extra space, only storing the ans variable and loop indices. It operates directly on the input and does not allocate additional space that depends on the input size. Therefore, the space complexity is O(1) as it remains constant regardless of the input size.

Learn more about how to find time and space complexity quickly using problem constraints.


Fast Track Your Learning with Our Quick Skills Quiz:

Which of the following array represent a max heap?


Recommended Readings


Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


🪄