We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Count Prefix and Suffix Pairs I

Number: 3309

Difficulty: Easy

Paid? No

Companies: Google, Autodesk

Problem Description

Given an array of strings words, count the number of index pairs (i, j) where i < j and words[i] is both a prefix and a suffix of words[j].

Key Insights

  • Iterate over all unique pairs (i, j) with i < j.
  • Check if words[i] is a prefix of words[j] by comparing words[j][0:len(words[i])] with words[i].
  • Check if words[i] is a suffix of words[j] by comparing words[j][-len(words[i]):] with words[i].
  • The constraints (n ≤ 50 and word length ≤ 10) allow a simple O(n²) solution.

Space and Time Complexity

Time Complexity: O(n² * m), where n is the number of words and m is the maximum length of a word. Space Complexity: O(1) extra space apart from the input.

Solution

The solution uses a nested loop to iterate over every pair (i, j) with i < j. For each pair, we verify that words[i] is both the prefix and the suffix of words[j] by comparing the relevant substrings. If both conditions hold, we increment the count. This approach is efficient given the small input size and leverages simple string operations.

Code Solutions

def countPrefixSuffixPairs(words):
    count = 0
    n = len(words)
    # Loop over each pair (i, j) with i < j
    for i in range(n):
        for j in range(i + 1, n):
            # Candidate substring from words[j] must be at least as long as words[i]
            if len(words[j]) < len(words[i]):
                continue
            # Check if words[i] is both prefix and suffix of words[j]
            if words[j][:len(words[i])] == words[i] and words[j][-len(words[i]):] == words[i]:
                count += 1
    return count

# Example usage
words = ["a", "aba", "ababa", "aa"]
print(countPrefixSuffixPairs(words))  # Output: 4
← Back to All Questions