Count Prefix and Suffix Pairs I

easy string prefix & suffix brute force

Problem

You are given a 0-indexed string array words. Define isPrefixAndSuffix(str1, str2) to be true when str1 is both a prefix and a suffix of str2 (for example isPrefixAndSuffix("aba", "ababa") is true). Return the number of index pairs (i, j) with i < j such that isPrefixAndSuffix(words[i], words[j]) is true.

Inputwords = ["a","aba","ababa","aa"]

Output4

Valid pairs: (0,1), (0,2), (0,3) since "a" prefixes & suffixes "aba", "ababa", "aa"; and (1,2) since "aba" prefixes & suffixes "ababa".

words (comma-separated)

def countPrefixSuffixPairs(words):
    # str1 must be BOTH a prefix and a suffix of str2.
    def is_prefix_and_suffix(s1, s2):
        return s2.startswith(s1) and s2.endswith(s1)

    count = 0
    n = len(words)
    for i in range(n):                 # left word of the pair
        for j in range(i + 1, n):      # right word, always after i
            if is_prefix_and_suffix(words[i], words[j]):
                count += 1             # this (i, j) pair qualifies
    return count

function countPrefixSuffixPairs(words) {
  // str1 must be BOTH a prefix and a suffix of str2.
  const isPrefixAndSuffix = (s1, s2) =>
    s2.startsWith(s1) && s2.endsWith(s1);

  let count = 0;
  const n = words.length;
  for (let i = 0; i < n; i++) {          // left word of the pair
    for (let j = i + 1; j < n; j++) {    // right word, always after i
      if (isPrefixAndSuffix(words[i], words[j])) {
        count++;                         // this (i, j) pair qualifies
      }
    }
  }
  return count;
}

int countPrefixSuffixPairs(String[] words) {
    int count = 0;
    int n = words.length;
    for (int i = 0; i < n; i++) {            // left word of the pair
        for (int j = i + 1; j < n; j++) {    // right word, always after i
            String a = words[i], b = words[j];
            // a must be BOTH a prefix and a suffix of b.
            if (b.startsWith(a) && b.endsWith(a)) {
                count++;                     // this (i, j) pair qualifies
            }
        }
    }
    return count;
}

int countPrefixSuffixPairs(vector<string>& words) {
    auto isPreSuf = [](const string& a, const string& b) {
        if (a.size() > b.size()) return false;          // a too long
        return b.compare(0, a.size(), a) == 0 &&        // prefix
               b.compare(b.size() - a.size(), a.size(), a) == 0; // suffix
    };
    int count = 0, n = words.size();
    for (int i = 0; i < n; i++) {            // left word of the pair
        for (int j = i + 1; j < n; j++) {    // right word, always after i
            if (isPreSuf(words[i], words[j])) count++;
        }
    }
    return count;
}

Explanation

This is a brute-force pair scan. Because the array is tiny (at most 50 words, each at most 10 characters), we can simply test every ordered pair directly instead of reaching for a trie or rolling hash.

The outer loop fixes the left index i, and the inner loop walks every later index j > i. This guarantees the requirement i < j for free and visits each unordered pair exactly once.

For a pair we evaluate isPrefixAndSuffix(words[i], words[j]). The candidate words[i] must match the start of words[j] (a prefix) and the end of words[j] (a suffix). In Python that is startswith plus endswith; in C++ we compare two slices of the longer string.

If words[i] is longer than words[j] it can be neither prefix nor suffix, so those pairs naturally fail. Every time both checks pass we increment count.

Example: for ["a","aba","ababa","aa"] the qualifying pairs are (0,1), (0,2), (0,3) and (1,2), so the answer is 4.

Time: O(n² · m) Space: O(1)