Count Prefix and Suffix Pairs I solution and explanation
Google
9 more videos on this problem
Count Prefix and Suffix Pairs I & II - Leetcode 3042 & 3045 - PythonNeetCodeIO · 20:54 · 12K views
3045 & 3042. Count Prefix and Suffix Pairs I & II | Trie | Hashing | Complete IntuitionAryan Mittal · 42:49 · 5K views
Count Prefix and Suffix Pairs I | Leetcode 3042Techdose · 10:32 · 3K views
Count Prefix and Suffix Pairs I | Leetcode 3042Ayushi Sharma · 11:31 · 1K views
3042. Count Prefix and Suffix Pairs I || Leetcode POTD || TriePrateek Goel · 6:51 · 976 views
3042. Count Prefix and Suffix Pairs I (Leetcode Easy)Programming Live with Larry · 3:38 · 334 views
Leetcode | 3042 Count Prefix and Suffix Pairs I | Java | BruteForce AppraochCakot Coding · 10:34 · 238 views
3042. Count Prefix and Suffix Pairs I | Leetcode Daily ChallengeEthos Typos · 9:21 · 174 views
LeetCode 3042 Count Prefix and Suffix Pairs I | Easy | String Matching | Asked in UberCode Harmony · 9:06 · 101 views
3042. Count Prefix and Suffix Pairs I || Leetcode || Day 1Viren Variya [IIIT-Delhi] · 8:33 · 100 views
The 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)returnstrueifstr1is both a prefix and a suffix ofstr2, andfalseotherwise.
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 <= 501 <= words[i].length <= 10words[i]consists only of lowercase English letters.
Approach overview
Problem Overview: You are given an array of strings words. Count pairs (i, j) where i < j and words[i] appears as both a prefix and a suffix of words[j]. The task reduces to checking whether one string matches the beginning and ending segments of another string.
Approach 1: Brute Force Comparison (Time: O(n^2 * m), Space: O(1))
Check every pair of strings. For each i and j where i < j, verify whether words[j] starts with words[i] and also ends with the same string. Most languages provide direct operations like startswith and endswith, which internally compare characters one by one. If both conditions hold, increment the count.
The complexity comes from examining every pair of words (O(n^2)) and performing string comparisons up to the length of the smaller word (O(m)). This approach works well for small inputs and clearly demonstrates the core logic of the problem. It relies only on basic array iteration and simple string operations.
Approach 2: Optimized Using String Matching / Hashing (Time: O(n^2), Space: O(n * m))
You can reduce repeated character comparisons by preprocessing strings with hashing or structured string-matching techniques. Using a rolling hash or prefix hash array, compute hash values for every prefix and suffix of each string. When comparing words[i] with words[j], compare their hash values instead of characters. If the prefix hash of length len(words[i]) in words[j] matches the full hash of words[i], and the suffix hash matches as well, the pair is valid.
This turns each prefix and suffix check into an O(1) operation after preprocessing. The overall pair iteration still takes O(n^2), but individual string comparisons become constant time. Techniques like string matching and rolling hash are commonly used in competitive programming to avoid repeated scans of the same substrings.
Recommended for interviews: Start with the brute force approach. It shows you understand the problem: iterate pairs and verify prefix and suffix conditions. Once that’s clear, mention the optimization using hashing or other string-matching techniques to avoid repeated character comparisons. Interviewers typically expect the simple pair-check solution first, followed by discussion of faster substring comparison strategies.
Approach 1: Brute Force Approach
This approach involves checking each possible pair of indices (i, j) to determine if words[i] is both a prefix and suffix of words[j]. We will simply iterate over all pairs of the words and apply the prefix and suffix condition.
def count_prefix_suffix_pairs(words):
def is_prefix_and_suffix(str1, str2):
prefix_match = str2.startswith(str1)
suffix_match = str2.endswith(str1)
return prefix_match and suffix_match
count = 0
n = len(words)
for i in range(n):
for j in range(i + 1, n):
if is_prefix_and_suffix(words[i], words[j]):
count += 1
return count
# Example usage
words = ["a","aba","ababa","aa"]
print(count_prefix_suffix_pairs(words)) # Output: 4import java.util.List;
public class CountPrefixSuffixPairs {
public static boolean isPrefixAndSuffix(String str1, String str2) {
if (str1.length() > str2.length()) return false;
return str2.startsWith(str1) && str2.endsWith(str1);
}
public static int countPrefixSuffixPairs(List<String> words) {
int count = 0;
for (int i = 0; i < words.size(); i++) {
for (int j = i + 1; j < words.size(); j++) {
if (isPrefixAndSuffix(words.get(i), words.get(j))) {
count++;
}
}
}
return count;
}
public static void main(String[] args) {
List<String> words = List.of("a", "aba", "ababa", "aa");
System.out.println(countPrefixSuffixPairs(words)); // Output: 4
}
}#include <iostream>
#include <vector>
#include <string>
using namespace std;
bool isPrefixAndSuffix(const string& str1, const string& str2) {
size_t len1 = str1.length();
size_t len2 = str2.length();
if (len1 > len2) return false;
return str2.substr(0, len1) == str1 && str2.substr(len2 - len1) == str1;
}
int countPrefixSuffixPairs(const vector<string>& words) {
int count = 0;
for (size_t i = 0; i < words.size(); ++i) {
for (size_t j = i + 1; j < words.size(); ++j) {
if (isPrefixAndSuffix(words[i], words[j])) {
++count;
}
}
}
return count;
}
int main() {
vector<string> words = {"a", "aba", "ababa", "aa"};
cout << countPrefixSuffixPairs(words) << endl; // Output: 4
return 0;
}function isPrefixAndSuffix(str1, str2) {
if (str1.length > str2.length) return false;
return str2.startsWith(str1) && str2.endsWith(str1);
}
function countPrefixSuffixPairs(words) {
let count = 0;
for (let i = 0; i < words.length; i++) {
for (let j = i + 1; j < words.length; j++) {
if (isPrefixAndSuffix(words[i], words[j])) {
count += 1;
}
}
}
return count;
}
// Example usage
const words = ["a","aba","ababa","aa"];
console.log(countPrefixSuffixPairs(words)); // Output: 4;#include <stdio.h>
#include <stdbool.h>
#include <string.h>
bool isPrefixAndSuffix(char* str1, char* str2) {
int len1 = strlen(str1);
int len2 = strlen(str2);
if (len1 > len2) return false;
return strncmp(str1, str2, len1) == 0 && strcmp(str1, str2 + len2 - len1) == 0;
}
int countPrefixSuffixPairs(char* words[], int wordsSize) {
int count = 0;
for (int i = 0; i < wordsSize; ++i) {
for (int j = i + 1; j < wordsSize; ++j) {
if (isPrefixAndSuffix(words[i], words[j])) {
++count;
}
}
}
return count;
}
int main() {
char* words[] = {"a", "aba", "ababa", "aa"};
int size = sizeof(words) / sizeof(words[0]);
int result = countPrefixSuffixPairs(words, size);
printf("%d\n", result); // Output: 4
return 0;
}using System;
using System.Collections.Generic;
class Program {
static bool IsPrefixAndSuffix(string str1, string str2) {
if (str1.Length > str2.Length) return false;
return str2.StartsWith(str1) && str2.EndsWith(str1);
}
static int CountPrefixSuffixPairs(List<string> words) {
int count = 0;
for (int i = 0; i < words.Count; i++) {
for (int j = i + 1; j < words.Count; j++) {
if (IsPrefixAndSuffix(words[i], words[j])) {
count++;
}
}
}
return count;
}
static void Main() {
List<string> words = new List<string> { "a", "aba", "ababa", "aa" };
Console.WriteLine(CountPrefixSuffixPairs(words)); // Output: 4
}
}This Python function counts the number of pairs (i, j) such that words[i] is both a prefix and suffix of words[j]. It defines a helper function is_prefix_and_suffix to perform this check and iterates over all pairs of the array to count the valid ones.
Time Complexity: O(n^2 * m), where n is the number of words and m is the average length of a word.
Space Complexity: O(1) as we are using constant extra space.
Approach 2: Optimized Approach Using String Matching
An optimized approach would require reducing the number of unnecessary comparisons. Since the constraints are small, a direct approach is feasible. However, if required, we can attempt to use advanced techniques such as hashing or Rabin-Karp algorithm for prefix-suffix matching which can potentially reduce time complexity by ensuring we're not redundantly checking characters.
def count_prefix_suffix_pairs(words):
def is_prefix_and_suffix(str1, str2):
if len(str1) > len(str2):
return False
return (str2.startswith(str1) and str2.endswith(str1))
from collections import defaultdict
prefix_dict = defaultdict(list)
for j, word in enumerate(words):
for i in range(1, len(word) + 1):
prefix_dict[word[:i]].append(j)
count = 0
for i, word in enumerate(words):
if len(word) <= 10:
suff_indices = prefix_dict[word]
for j in suff_indices:
if i < j and words[j].endswith(word):
count += 1
return count
# Example usage
words = ["a","aba","ababa","aa"]
print(count_prefix_suffix_pairs(words)) # Output: 4import java.util.*;
public class OptimizedCount {
public static boolean isPrefixAndSuffix(String str1, String str2) {
if (str1.length() > str2.length()) return false;
return str2.startsWith(str1) && str2.endsWith(str1);
}
public static int countPrefixSuffixPairs(List<String> words) {
Map<String, List<Integer>> prefixMap = new HashMap<>();
int length = words.size();
for (int j = 0; j < length; j++) {
String word = words.get(j);
for (int i = 1; i <= word.length(); i++) {
String prefix = word.substring(0, i);
if (!prefixMap.containsKey(prefix)) {
prefixMap.put(prefix, new ArrayList<>());
}
prefixMap.get(prefix).add(j);
}
}
int count = 0;
for (int i = 0; i < length; i++) {
List<Integer> indices = prefixMap.get(words.get(i));
if (indices != null) {
for (int j : indices) {
if (i < j && words.get(j).endsWith(words.get(i))) {
count++;
}
}
}
}
return count;
}
public static void main(String[] args) {
List<String> words = Arrays.asList("a", "aba", "ababa", "aa");
System.out.println(countPrefixSuffixPairs(words)); // Output: 4
}
}This optimized Python solution preprocesses each word to store all possible prefixes in a dictionary. Then for each word, it fetches potential matches from the dictionary where words are prefixes and checks them for suffix property.
Time Complexity: O(n * m), where n is the number of words and m is the average length of a word. The improvement comes from reducing unnecessary suffix checks.
Space Complexity: O(n * m) due to storing prefixes.
Approach 3: Enumeration
We can enumerate all index pairs (i, j), where i < j, and then determine whether words[i] is a prefix or suffix of words[j]. If it is, we increment the count.
The time complexity is O(n^2 times m), where n and m are the length of words and the maximum length of the strings, respectively.
function countPrefixSuffixPairs(words: string[]): number {
let ans = 0;
for (let i = 0; i < words.length; ++i) {
const s = words[i];
for (const t of words.slice(i + 1)) {
if (t.startsWith(s) && t.endsWith(s)) {
++ans;
}
}
}
return ans;
}func countPrefixSuffixPairs(words []string) (ans int) {
for i, s := range words {
for _, t := range words[i+1:] {
if strings.HasPrefix(t, s) && strings.HasSuffix(t, s) {
ans++
}
}
}
return
}Approach 4: Trie
We can treat each string s in the string array as a list of character pairs, where each character pair (s[i], s[m - i - 1]) represents the ith character pair of the prefix and suffix of string s.
We can use a trie to store all the character pairs, and then for each string s, we search for all the character pairs (s[i], s[m - i - 1]) in the trie, and add their counts to the answer.
The time complexity is O(n times m), and the space complexity is O(n times m). Here, n and m are the lengths of words and the maximum length of the strings, respectively.
type Node struct {
children map[int]*Node
cnt int
}
func countPrefixSuffixPairs(words []string) (ans int) {
trie := &Node{children: make(map[int]*Node)}
for _, s := range words {
node := trie
m := len(s)
for i := 0; i < m; i++ {
p := int(s[i])*32 + int(s[m-i-1])
if _, ok := node.children[p]; !ok {
node.children[p] = &Node{children: make(map[int]*Node)}
}
node = node.children[p]
ans += node.cnt
}
node.cnt++
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(n^2 * m), where n is the number of words and m is the average length of a word. |
| Optimized Approach Using String Matching | Time Complexity: O(n * m), where n is the number of words and m is the average length of a word. The improvement comes from reducing unnecessary suffix checks. |
| Enumeration | – |
| Trie | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Prefix & Suffix Check | O(n^2 * m) | O(1) | Best for understanding the problem or when constraints are small |
| Rolling Hash / String Matching Optimization | O(n^2) | O(n * m) | When repeated string comparisons are expensive and faster substring checks are needed |
Frequently asked questions
Is Count Prefix and Suffix Pairs I easy or hard?
Count Prefix and Suffix Pairs I is classified as an Easy problem on LeetCode with a high acceptance rate around 77%. The logic is straightforward once you recognize that the task is simply verifying prefix and suffix matches between pairs of strings.
Count Prefix and Suffix Pairs I Python/Java solution
Python solutions typically use built-in methods like startswith() and endswith() inside nested loops. Java implementations use startsWith() and endsWith() from the String class. Both follow the same O(n^2 * m) logic and are easy to implement for interview settings.
How to solve Count Prefix and Suffix Pairs I in O(n)?
A strict O(n) solution is not typical because the problem requires comparing multiple pairs of strings. However, you can reduce repeated comparisons using rolling hash or prefix hashing so each prefix/suffix validation becomes constant time. The overall algorithm still iterates through pairs but performs much faster checks.
What is the best approach for Count Prefix and Suffix Pairs I?
The most practical approach checks every pair of words and verifies whether one string is both the prefix and suffix of the other. This brute force method runs in O(n^2 * m) time, where n is the number of words and m is the average string length. For larger inputs, rolling hash or other string matching techniques can reduce comparison cost.
Is Count Prefix and Suffix Pairs I asked at Google/Amazon/Meta?
String matching and prefix–suffix problems frequently appear in interviews at companies like Google, Amazon, and Meta. While this exact question may vary, the concepts—string comparison, hashing, and prefix-suffix relationships—are common interview topics.
What data structure is used in Count Prefix and Suffix Pairs I?
The basic solution relies on arrays and string operations. Optimized approaches may use rolling hash arrays, hash functions, or even a Trie structure to efficiently match prefixes and suffixes across multiple strings.
What is the time complexity of Count Prefix and Suffix Pairs I?
The straightforward solution runs in O(n^2 * m) time because every pair of words is compared and each prefix/suffix check may scan up to m characters. With hashing or optimized string matching, prefix and suffix checks can become O(1), reducing the overall complexity to about O(n^2) after preprocessing.