8_Count_Prefix_and_Suffix_Pairs_I.cpp

// 3042. Count Prefix and Suffix Pairs I

// 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

class Solution
{
public:
    bool isPrefixAndSuffix(const string &str1, const string &str2)
    {
        int n1 = str1.size(), n2 = str2.size();
        if (n1 > n2)
            return false;
        return str2.substr(0, n1) == str1 && str2.substr(n2 - n1) == str1;
    }

    int countPrefixSuffixPairs(vector<string> &words)
    {
        int n = words.size(), count = 0;
        for (int i = 0; i < n; ++i)
        {
            for (int j = i + 1; j < n; ++j)
            {
                if (isPrefixAndSuffix(words[i], words[j]))
                {
                    ++count;
                }
            }
        }
        return count;
    }
};

/*
This code solves the problem of counting prefix-suffix pairs in an array of strings. Here's how it works:

1. isPrefixAndSuffix function:
   - Takes two strings and checks if str1 is both prefix and suffix of str2
   - First checks if str1 is longer than str2 (returns false if true)
   - Uses substr to check if str1 matches both the beginning and end of str2

2. countPrefixSuffixPairs function:
   - Uses nested loops to compare each pair of strings (i,j) where i < j
   - For each pair, calls isPrefixAndSuffix to check the condition
   - Maintains a counter that increments when a valid pair is found
   - Returns the final count of valid pairs

Time Complexity: O(n^2 * m) where n is array length and m is average string length
Space Complexity: O(1) as it uses only constant extra space
*/