Count Prefix and Suffix Pairs II solution and explanation
8 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
3045. Count Prefix and Suffix Pairs II | Weekly Leetcode 385codingMohan · 46:04 · 1K views
3045. Count Prefix and Suffix Pairs II (Leetcode Hard)Programming Live with Larry · 23:56 · 627 views
【每日一题】LeetCode 3045. Count Prefix and Suffix Pairs IIHuifeng Guan · 35:10 · 432 views
Day 35/75: Problem Name: Count Prefix and Suffix Pairs II | Leetcode | #75DaysHardLC | Weekly 385CodeInsanity · 12:16 · 204 views
LeetCode 3045 - Count Prefix and Suffix Pairs II - PythonAlpha-Code · 22:48 · 149 views
3045. Count Prefix and Suffix Pairs II | Trie | Google | LeetcodeHimani · 17:15 · 77 views
Leetcode Weekly Contest 385 Problem Count Prefix and Suffix Pairs II Leetcode Contact 385 Problem Dcode conqueror · 0:07 · 11 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 <= 1051 <= words[i].length <= 105words[i]consists only of lowercase English letters.- The sum of the lengths of all
words[i]does not exceed5 * 105.
Approach overview
Problem Overview: You are given an array of strings. Count pairs (i, j) such that i < j and words[i] is both a prefix and a suffix of words[j]. The challenge comes from large input sizes, which makes naive pairwise string comparison too slow.
Approach 1: Brute Force String Comparison (O(n^2 · m) time, O(1) space)
Check every pair of indices (i, j) with i < j. For each pair, verify whether words[i] matches both the prefix and suffix of words[j]. Prefix comparison checks the first len(words[i]) characters, while suffix comparison checks the last len(words[i]). Each comparison costs up to O(m) where m is the string length. This results in O(n^2 · m) total time. The approach is straightforward and useful for understanding the requirement, but it becomes impractical when the number of strings grows.
Approach 2: Optimized Rolling Hash Matching (O(totalLength) average time, O(n) space)
Instead of comparing strings character by character, compute rolling hash values for prefixes and suffixes of each word. While scanning a word, build prefix and suffix hashes simultaneously. Whenever the prefix hash equals the suffix hash for length k, the substring is both a prefix and suffix candidate. Store previously seen words in a hash map keyed by their hash value. A constant-time hash lookup tells you how many earlier strings match the current prefix–suffix substring. This converts expensive string comparisons into fast integer comparisons.
The key idea: a string that is both prefix and suffix must have identical hash values from both directions. With precomputed powers and incremental hashing, each character contributes once, giving near linear complexity across all strings.
Some implementations also use a trie or prefix tree to track prefixes efficiently, but hashing usually gives simpler code and excellent performance.
Recommended for interviews: Start by explaining the brute force solution to show you understand the pair condition and prefix/suffix check. Then move to the hashing optimization. Interviewers expect you to eliminate repeated string comparisons using hashing or a string processing technique. The optimized approach demonstrates knowledge of rolling hashes and efficient substring matching.
Approach 1: Brute Force Approach
This approach involves iterating through each pair of strings and checking if one is both a prefix and suffix of the other. Although this might be simple to implement, it can be computationally expensive for large inputs.
def is_prefix_and_suffix(str1, str2):
if len(str1) > len(str2):
return False
return str2.startswith(str1) and str2.endswith(str1)
def count_prefix_and_suffix_pairs(words):
count = 0
for i in range(len(words)):
for j in range(i + 1, len(words)):
if is_prefix_and_suffix(words[i], words[j]):
count += 1
return count
words = ["a", "aba", "ababa", "aa"]
print(count_prefix_and_suffix_pairs(words))import java.util.*;
public class Main {
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 countPrefixAndSuffixPairs(String[] words) {
int count = 0;
for (int i = 0; i < words.length; i++) {
for (int j = i + 1; j < words.length; j++) {
if (isPrefixAndSuffix(words[i], words[j]))
count++;
}
}
return count;
}
public static void main(String[] args) {
String[] words = {"a", "aba", "ababa", "aa"};
System.out.println(countPrefixAndSuffixPairs(words));
}
}#include <iostream>
#include <vector>
bool isPrefixAndSuffix(const std::string& str1, const std::string& str2) {
if (str1.length() > str2.length()) return false;
return str2.compare(0, str1.length(), str1) == 0 &&
str2.compare(str2.length() - str1.length(), str1.length(), str1) == 0;
}
int countPrefixAndSuffixPairs(const std::vector<std::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() {
std::vector<std::string> words = {"a", "aba", "ababa", "aa"};
std::cout << countPrefixAndSuffixPairs(words) << std::endl;
return 0;
}function isPrefixAndSuffix(str1, str2) {
if (str1.length > str2.length) return false;
return str2.startsWith(str1) && str2.endsWith(str1);
}
function countPrefixAndSuffixPairs(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++;
}
}
return count;
}
const words = ["a", "aba", "ababa", "aa"];
console.log(countPrefixAndSuffixPairs(words));#include <stdio.h>
#include <string.h>
int isPrefixAndSuffix(char* str1, char* str2) {
int len1 = strlen(str1);
int len2 = strlen(str2);
if (len1 > len2) return 0;
return strncmp(str1, str2, len1) == 0 && strncmp(str1, str2 + len2 - len1, len1) == 0;
}
int countPrefixAndSuffixPairs(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 result = countPrefixAndSuffixPairs(words, 4);
printf("%d\n", result);
return 0;
}using System;
public class MainClass {
public static bool IsPrefixAndSuffix(string str1, string str2) {
if (str1.Length > str2.Length) return false;
return str2.StartsWith(str1) && str2.EndsWith(str1);
}
public static int CountPrefixAndSuffixPairs(string[] words) {
int count = 0;
for (int i = 0; i < words.Length; i++) {
for (int j = i + 1; j < words.Length; j++) {
if (IsPrefixAndSuffix(words[i], words[j]))
count++;
}
}
return count;
}
public static void Main(string[] args) {
string[] words = {"a", "aba", "ababa", "aa"};
Console.WriteLine(CountPrefixAndSuffixPairs(words));
}
}Python's startswith and endswith methods are utilized to determine if one string is both prefix and suffix of another. The solution involves nested loops to find all such pairs.
Time Complexity: O(n^2 * m). Space Complexity: O(1).
Approach 2: Optimized Approach Using Hashing
This approach utilizes hashing to optimize the searching of potential prefix and suffix pairs. By hashing potential prefixes and suffixes, we can reduce redundant checks, improving efficiency.
def count_prefix_and_suffix_pairs(words):
count = 0
seen = set()
for j in range(len(words)):
for i in range(j):
if len(words[i]) <= len(words[j]):
if words[i] in seen:
count += 1
seen.add(words[j])
return count
words = ["a", "aba", "ababa", "aa"]
print(count_prefix_and_suffix_pairs(words))import java.util.*;
public class Main {
public static int countPrefixAndSuffixPairs(String[] words) {
int count = 0;
Set<String> seen = new HashSet<>();
for (int j = 0; j < words.length; j++) {
for (int i = 0; i < j; i++) {
if (words[i].length() <= words[j].length()) {
if (seen.contains(words[i])) {
count++;
}
}
}
seen.add(words[j]);
}
return count;
}
public static void main(String[] args) {
String[] words = {"a", "aba", "ababa", "aa"};
System.out.println(countPrefixAndSuffixPairs(words));
}
}#include <iostream>
#include <unordered_set>
#include <string>
#include <vector>
int countPrefixAndSuffixPairs(const std::vector<std::string>& words) {
int count = 0;
std::unordered_set<std::string> seen;
for (size_t j = 0; j < words.size(); ++j) {
int lenJ = words[j].length();
for (size_t i = 0; i < j; ++i) {
if (words[i].length() <= lenJ) {
if (seen.find(words[i]) != seen.end()) {
++count;
}
}
}
seen.insert(words[j]);
}
return count;
}
int main() {
std::vector<std::string> words = {"a", "aba", "ababa", "aa"};
std::cout << countPrefixAndSuffixPairs(words) << std::endl;
return 0;
}function countPrefixAndSuffixPairs(words) {
let count = 0;
const seen = new Set();
for (let j = 0; j < words.length; j++) {
for (let i = 0; i < j; i++) {
if (words[i].length <= words[j].length) {
if (seen.has(words[i])) {
count++;
}
}
}
seen.add(words[j]);
}
return count;
}
const words = ["a", "aba", "ababa", "aa"];
console.log(countPrefixAndSuffixPairs(words));#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAXN 100000
#define HASHSIZE 100003
typedef struct Node {
char *word;
struct Node *next;
} Node;
Node *hashTable[HASHSIZE];
unsigned int hash(const char *word) {
unsigned int h = 0;
while (*word) h = (h * 31 + *word++) % HASHSIZE;
return h;
}
void insert(const char *word) {
unsigned int h = hash(word);
Node *node = (Node *)malloc(sizeof(Node));
node->word = strdup(word);
node->next = hashTable[h];
hashTable[h] = node;
}
int search(const char *word) {
unsigned int h = hash(word);
Node *p = hashTable[h];
while (p) {
if (strcmp(p->word, word) == 0) return 1;
p = p->next;
}
return 0;
}
void freeHashTable() {
for (int i = 0; i < HASHSIZE; i++) {
Node *node = hashTable[i];
while (node) {
Node *temp = node;
node = node->next;
free(temp->word);
free(temp);
}
}
}
int countPrefixAndSuffixPairs(char **words, int wordsSize) {
memset(hashTable, 0, sizeof(hashTable));
int count = 0;
for (int j = 0; j < wordsSize; j++) {
int lenJ = strlen(words[j]);
for (int i = 0; i < wordsSize; i++) {
if (i < j && strlen(words[i]) <= lenJ) {
if (search(words[i]))
count++;
}
}
insert(words[j]);
}
freeHashTable();
return count;
}
int main() {
char *words[] = {"a", "aba", "ababa", "aa"};
int result = countPrefixAndSuffixPairs(words, 4);
printf("%d\n", result);
return 0;
}using System;
using System.Collections.Generic;
public class MainClass {
public static int CountPrefixAndSuffixPairs(string[] words) {
int count = 0;
HashSet<string> seen = new HashSet<string>();
for (int j = 0; j < words.Length; j++) {
for (int i = 0; i < j; i++) {
if (words[i].Length <= words[j].Length) {
if (seen.Contains(words[i])) {
count++;
}
}
}
seen.Add(words[j]);
}
return count;
}
public static void Main(string[] args) {
string[] words = {"a", "aba", "ababa", "aa"};
Console.WriteLine(CountPrefixAndSuffixPairs(words));
}
}Using Python's set improves efficiency by leveraging fast membership testing and insertions, significantly reducing time complexity.
Time Complexity: O(n * m). Space Complexity: O(n * m).
Approach 3: Naive Brute Force Approach
In this approach, we iterate over all possible pairs of indices (i, j) with i < j and check whether the word at index i is both a prefix and a suffix of the word at index j. Although simple, this approach is inefficient for large datasets due to its O(n*m) complexity, where n is the number of words and m is the average length of the words.
def isPrefixAndSuffix(prefix, string):
if len(prefix) > len(string):
return False
return string.startswith(prefix) and string.endswith(prefix)
def countPrefixSuffixPairs(words):
count = 0
for i in range(len(words)):
for j in range(i + 1, len(words)):
if isPrefixAndSuffix(words[i], words[j]):
count += 1
return count
words = ["a", "aba", "ababa", "aa"]
print(countPrefixSuffixPairs(words))import java.util.*;
public class Main {
public static boolean isPrefixAndSuffix(String prefix, String str) {
int lenPref = prefix.length();
int lenStr = str.length();
if (lenPref > lenStr) return false;
return str.startsWith(prefix) && str.endsWith(prefix);
}
public static int countPrefixSuffixPairs(String[] words) {
int count = 0;
for (int i = 0; i < words.length; i++) {
for (int j = i + 1; j < words.length; j++) {
if (isPrefixAndSuffix(words[i], words[j])) {
count++;
}
}
}
return count;
}
public static void main(String[] args) {
String[] words = {"a", "aba", "ababa", "aa"};
System.out.println(countPrefixSuffixPairs(words));
}
}#include <iostream>
#include <vector>
using namespace std;
bool isPrefixAndSuffix(const string &prefix, const string &str) {
int lenPref = prefix.length();
int lenStr = str.length();
if (lenPref > lenStr) return false;
return (str.substr(0, lenPref) == prefix && str.substr(lenStr - lenPref) == prefix);
}
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;
return 0;
}function isPrefixAndSuffix(prefix, string) {
if (prefix.length > string.length) return false;
return string.startsWith(prefix) && string.endsWith(prefix);
}
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++;
}
}
}
return count;
}
const words = ["a", "aba", "ababa", "aa"];
console.log(countPrefixSuffixPairs(words));#include <stdio.h>
#include <string.h>
int isPrefixAndSuffix(char *prefix, char *str) {
int lenPref = strlen(prefix);
int lenStr = strlen(str);
if (lenPref > lenStr) return 0;
for (int i = 0; i < lenPref; ++i) {
if (prefix[i] != str[i] || prefix[i] != str[lenStr - lenPref + i]) return 0;
}
return 1;
}
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 wordsSize = sizeof(words) / sizeof(words[0]);
printf("%d\n", countPrefixSuffixPairs(words, wordsSize));
return 0;
}using System;
class Program {
public static bool IsPrefixAndSuffix(string prefix, string str) {
int lenPref = prefix.Length;
int lenStr = str.Length;
if (lenPref > lenStr) return false;
return str.StartsWith(prefix) && str.EndsWith(prefix);
}
public static int CountPrefixSuffixPairs(string[] words) {
int count = 0;
for (int i = 0; i < words.Length; i++) {
for (int j = i + 1; j < words.Length; j++) {
if (IsPrefixAndSuffix(words[i], words[j])) {
count++;
}
}
}
return count;
}
public static void Main() {
string[] words = { "a", "aba", "ababa", "aa" };
Console.WriteLine(CountPrefixSuffixPairs(words));
}
}The Python solution employs the list data structure to store words and validates each pair using pre-existing string methods `startswith` and `endswith` for prefix and suffix checks respectively.
The time complexity is O(n^2 * m) given the nested loops and string operation costs, and the space complexity is O(1).
Approach 4: Optimized Approach Using KMP Algorithm
The Knuth-Morris-Pratt (KMP) algorithm can be used to find if a string is a prefix and suffix by preprocessing the pattern and avoiding redundant checks. The prefix function used in KMP gives valuable insight into repeated patterns in a string.
def compute_lps_array(pat):
lps = [0] * len(pat)
length = 0 # length of the previous longest prefix suffix
i = 1
while i < len(pat):
if pat[i] == pat[length]:
length += 1
lps[i] = length
i += 1
else:
if length != 0:
length = lps[length - 1]
else:
lps[i] = 0
i += 1
return lps
def is_prefix_and_suffix_kmp(prefix, string):
if len(prefix) > len(string):
return False
combined = prefix + "#" + string
lps = compute_lps_array(combined)
return lps[-1] >= len(prefix)
def count_prefix_suffix_pairs_kmp(words):
count = 0
for i in range(len(words)):
for j in range(i + 1, len(words)):
if is_prefix_and_suffix_kmp(words[i], words[j]):
count += 1
return count
words = ["a", "aba", "ababa", "aa"]
print(count_prefix_suffix_pairs_kmp(words))import java.util.*;
public class Main {
private static void computeLPSArray(String pattern, int[] lps) {
int len = 0;
int i = 1;
lps[0] = 0;
while (i < pattern.length()) {
if (pattern.charAt(i) == pattern.charAt(len)) {
len++;
lps[i++] = len;
} else {
if (len != 0) {
len = lps[len - 1];
} else {
lps[i++] = 0;
}
}
}
}
private static boolean isPrefixAndSuffixKMP(String prefix, String str) {
if (prefix.length() > str.length()) return false;
String combined = prefix + "#" + str;
int[] lps = new int[combined.length()];
computeLPSArray(combined, lps);
return lps[combined.length() - 1] >= prefix.length();
}
public static int countPrefixSuffixPairsKMP(String[] words) {
int count = 0;
for (int i = 0; i < words.length; i++) {
for (int j = i + 1; j < words.length; j++) {
if (isPrefixAndSuffixKMP(words[i], words[j])) {
count++;
}
}
}
return count;
}
public static void main(String[] args) {
String[] words = { "a", "aba", "ababa", "aa" };
System.out.println(countPrefixSuffixPairsKMP(words));
}
}#include <iostream>
#include <vector>
#include <string>
using namespace std;
void computeLPSArray(const string &str, vector<int> &lps) {
int M = str.length();
int length = 0;
lps[0] = 0;
int i = 1;
while (i < M) {
if (str[i] == str[length]) {
length++;
lps[i++] = length;
} else {
if (length != 0) {
length = lps[length - 1];
} else {
lps[i++] = 0;
}
}
}
}
bool isPrefixAndSuffixKMP(const string &prefix, const string &str) {
int lenPref = prefix.length();
int lenStr = str.length();
if (lenPref > lenStr) return false;
string combined = prefix + "#" + str;
vector<int> lps(combined.length(), 0);
computeLPSArray(combined, lps);
return lps.back() >= lenPref;
}
int countPrefixSuffixPairsKMP(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 (isPrefixAndSuffixKMP(words[i], words[j])) {
count++;
}
}
}
return count;
}
int main() {
vector<string> words = {"a", "aba", "ababa", "aa"};
cout << countPrefixSuffixPairsKMP(words) << endl;
return 0;
}function computeLPSArray(pattern) {
let lps = Array(pattern.length).fill(0);
let len = 0;
let i = 1;
while (i < pattern.length) {
if (pattern[i] == pattern[len]) {
len++;
lps[i++] = len;
} else {
if (len != 0) {
len = lps[len - 1];
} else {
lps[i++] = 0;
}
}
}
return lps;
}
function isPrefixAndSuffixKMP(prefix, str) {
if (prefix.length > str.length) return false;
let combined = prefix + '#' + str;
let lps = computeLPSArray(combined);
return lps[lps.length - 1] >= prefix.length;
}
function countPrefixSuffixPairsKMP(words) {
let count = 0;
for (let i = 0; i < words.length; i++) {
for (let j = i + 1; j < words.length; j++) {
if (isPrefixAndSuffixKMP(words[i], words[j])) {
count++;
}
}
}
return count;
}
let words = ["a", "aba", "ababa", "aa"];
console.log(countPrefixSuffixPairsKMP(words));#include <stdio.h>
#include <string.h>
#include <stdbool.h>
void computeLPSArray(const char* str, int M, int* lps) {
int length = 0;
int i = 1;
lps[0] = 0;
while (i < M) {
if (str[i] == str[length]) {
length++;
lps[i] = length;
i++;
} else {
if (length != 0) {
length = lps[length - 1];
} else {
lps[i] = 0;
i++;
}
}
}
}
bool isPrefixAndSuffixKMP(const char* prefix, const char* str) {
int lenPrefix = strlen(prefix);
int lenStr = strlen(str);
if (lenPrefix > lenStr) return false;
// Compute the concatenated string selfCheck
char concat[strlen(prefix) + strlen(str) + 1];
sprintf(concat, "%s#%s", prefix, str);
// Compute LPS array for the concatenated string
int lps[strlen(concat)];
computeLPSArray(concat, strlen(concat), lps);
// The prefix and suffix must match completely in the concatenated string
return lps[strlen(concat) - 1] >= lenPrefix;
}
int countPrefixSuffixPairsKMP(char* words[], int wordsSize) {
int count = 0;
for (int i = 0; i < wordsSize; ++i) {
for (int j = i + 1; j < wordsSize; ++j) {
if (isPrefixAndSuffixKMP(words[i], words[j])) {
count++;
}
}
}
return count;
}
int main() {
char* words[] = {"a", "aba", "ababa", "aa"};
int wordsSize = sizeof(words) / sizeof(words[0]);
printf("%d\n", countPrefixSuffixPairsKMP(words, wordsSize));
return 0;
}using System;
class Program {
static void ComputeLPSArray(string pattern, int[] lps) {
int len = 0;
lps[0] = 0;
int i = 1;
while (i < pattern.Length) {
if (pattern[i] == pattern[len]) {
len++;
lps[i++] = len;
} else {
if (len != 0) {
len = lps[len - 1];
} else {
lps[i++] = 0;
}
}
}
}
static bool IsPrefixAndSuffixKMP(string prefix, string str) {
if (prefix.Length > str.Length) return false;
string combined = prefix + "#" + str;
int[] lps = new int[combined.Length];
ComputeLPSArray(combined, lps);
return lps[combined.Length - 1] >= prefix.Length;
}
static int CountPrefixSuffixPairsKMP(string[] words) {
int count = 0;
for (int i = 0; i < words.Length; i++) {
for (int j = i + 1; j < words.Length; j++) {
if (IsPrefixAndSuffixKMP(words[i], words[j])) {
count++;
}
}
}
return count;
}
static void Main() {
string[] words = { "a", "aba", "ababa", "aa" };
Console.WriteLine(CountPrefixSuffixPairsKMP(words));
}
}The Python implementation leverages KMP's LPS array to efficiently match prefix and suffix conditions in a scalable manner.
With O(n * m) time complexity, the method efficiently handles inputs using an O(m) space LPS array.
Approach 5: 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.
class Node {
children: Map<number, Node> = new Map<number, Node>();
cnt: number = 0;
}
function countPrefixSuffixPairs(words: string[]): number {
let ans: number = 0;
const trie: Node = new Node();
for (const s of words) {
let node: Node = trie;
const m: number = s.length;
for (let i: number = 0; i < m; ++i) {
const p: number = s.charCodeAt(i) * 32 + s.charCodeAt(m - i - 1);
if (!node.children.has(p)) {
node.children.set(p, new Node());
}
node = node.children.get(p)!;
ans += node.cnt;
}
++node.cnt;
}
return ans;
}type Node struct {
children map[int]*Node
cnt int
}
func countPrefixSuffixPairs(words []string) (ans int64) {
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 += int64(node.cnt)
}
node.cnt++
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(n^2 * m). Space Complexity: O(1). |
| Optimized Approach Using Hashing | Time Complexity: O(n * m). Space Complexity: O(n * m). |
| Naive Brute Force Approach | The time complexity is O(n^2 * m) given the nested loops and string operation costs, and the space complexity is O(1). |
| Optimized Approach Using KMP Algorithm | With O(n * m) time complexity, the method efficiently handles inputs using an O(m) space LPS array. |
| Trie | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force String Comparison | O(n^2 · m) | O(1) | Small input sizes or when demonstrating the basic idea in interviews |
| Rolling Hash with Hash Map | O(total string length) | O(n) | Large inputs where repeated prefix/suffix comparisons must be avoided |
Frequently asked questions
Is Count Prefix and Suffix Pairs II easy or hard?
Count Prefix and Suffix Pairs II is classified as a Hard problem. The difficulty comes from large constraints and the need to replace naive comparisons with hashing or advanced string matching techniques.
Count Prefix and Suffix Pairs II Python/Java solution
Python and Java solutions typically implement rolling hash with precomputed powers and a hash map storing previously seen strings. As each word is processed, prefix and suffix hashes are compared and matched against the map. This keeps the algorithm close to linear time.
How to solve Count Prefix and Suffix Pairs II in O(n)?
Process each word while maintaining rolling hashes for its prefixes and suffixes. When both hashes match for a certain length, the substring is both prefix and suffix. Use a hash map storing previously processed words by hash value to count matches in constant time. This avoids pairwise comparisons and scales linearly with the total input size.
What is the best approach for Count Prefix and Suffix Pairs II?
The most efficient approach uses rolling hash combined with a hash map. While scanning each word, compute prefix and suffix hashes and check when they match. Each matching prefix-suffix substring can be looked up in a map of previously seen words, allowing the pair count to be updated in constant time.
Is Count Prefix and Suffix Pairs II asked at Google/Amazon/Meta?
Problems involving prefix-suffix matching, rolling hashes, and trie structures appear frequently in interviews at companies like Google, Amazon, and Meta. Variants of this problem test knowledge of string hashing, substring matching, and efficient counting techniques.
What data structure is used in Count Prefix and Suffix Pairs II?
Common solutions use a hash map with rolling hash values to represent strings efficiently. Some implementations also use a trie to track prefixes and detect matches while inserting characters. Both approaches aim to avoid repeated string comparisons.
What is the time complexity of Count Prefix and Suffix Pairs II?
The brute force solution runs in O(n^2 · m) where n is the number of strings and m is the average string length. The optimized rolling hash approach processes characters once and performs constant-time hash lookups, resulting in roughly O(total string length) time with O(n) extra space.