Skip to main content
Talentd

Number of Prefix Connected Groups - Solution & Explanation

MediumArrayHash TableStringCounting7 min read
Practice this problem

Problem Statement

You are given an array of strings words and an integer k.

Two words a and b at distinct indices are prefix-connected if a[0..k-1] == b[0..k-1].

A connected group is a set of words such that each pair of words is prefix-connected.

Return the number of connected groups that contain at least two words, formed from the given words.

Note:

  • Words with length less than k cannot join any group and are ignored.
  • Duplicate strings are treated as separate words.

 

Example 1:

Input: words = ["apple","apply","banana","bandit"], k = 2

Output: 2

Explanation:

Words sharing the same first k = 2 letters are grouped together:

  • words[0] = "apple" and words[1] = "apply" share prefix "ap".
  • words[2] = "banana" and words[3] = "bandit" share prefix "ba".

Thus, there are 2 connected groups, each containing at least two words.

Example 2:

Input: words = ["car","cat","cartoon"], k = 3

Output: 1

Explanation:

Words are evaluated for a prefix of length k = 3:

  • words[0] = "car" and words[2] = "cartoon" share prefix "car".
  • words[1] = "cat" does not share a 3-length prefix with any other word.

Thus, there is 1 connected group.

Example 3:

Input: words = ["bat","dog","dog","doggy","bat"], k = 3

Output: 2

Explanation:

Words are evaluated for a prefix of length k = 3:

  • words[0] = "bat" and words[4] = "bat" form a group.
  • words[1] = "dog", words[2] = "dog" and words[3] = "doggy" share prefix "dog".

Thus, there are 2 connected groups, each containing at least two words.

 

Constraints:

  • 1 <= words.length <= 5000
  • 1 <= words[i].length <= 100
  • 1 <= k <= 100
  • All strings in words consist of lowercase English letters.

Approach Overview

Problem Overview: You receive an array of strings. Two strings belong to the same group if one string is a prefix of another. The task is to count how many distinct prefix-connected groups exist after considering all strings.

Approach 1: Pairwise Prefix Comparison (Brute Force) (Time: O(n^2 * L), Space: O(1))

The direct strategy compares every pair of strings and checks whether one is a prefix of the other. For each pair, iterate character by character until the prefix relationship either matches or fails. If a connection exists, mark them as belonging to the same group using simple visited/group markers. This works for small inputs but becomes slow because every pair of strings is examined. The repeated prefix checks make the runtime quadratic with respect to the number of strings.

Approach 2: Hash Table with Prefix Tracking (Optimal) (Time: O(n * L), Space: O(n))

Use a hash table to store strings that have already been processed. For each word, generate its prefixes from shortest to longest and check if any prefix already exists in the hash set. If a prefix is found, the current string belongs to that existing group. If none of its prefixes exist, this string starts a new group. Insert the full string into the hash table so later strings can connect through it. Since prefix generation costs O(L) per string and hash lookups are O(1) on average, the total complexity becomes O(n * L).

This method leverages the fact that prefix relationships can be detected incrementally while scanning the array once. Instead of comparing every pair, you only examine the prefixes of the current string and perform constant‑time membership checks in the hash structure. The idea is closely related to prefix detection used in string problems and frequency tracking from counting techniques.

Recommended for interviews: Interviewers expect the hash table approach. The brute force solution demonstrates that you understand the prefix relationship definition, but the optimized method shows you can eliminate redundant comparisons using hashing. Recognizing that previously seen prefixes can represent entire groups is the key insight.

Solution

We use a hash table cnt to count the number of occurrences of the prefix composed of the first k characters of each string with length greater than or equal to k. Finally, we count the number of keys in cnt with values greater than 1, which is the number of connected groups.

The time complexity is O(n times k), and the space complexity is O(n), where n is the length of words.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Pairwise Prefix ComparisonO(n^2 * L)O(1)Useful for understanding the prefix relationship or when input size is very small
Hash Table with Prefix TrackingO(n * L)O(n)General case and interview scenarios where efficient prefix detection is required

Video Solution

LeetCode Problem 3839 | Number of Prefix Connected Groups • Repovive TV • 64 views views

Watch 4 more video solutions →

Frequently Asked Questions

Is Number of Prefix Connected Groups easy or hard?
The problem is considered Medium difficulty. The main challenge is recognizing that prefix relationships can be detected incrementally with a hash table rather than comparing every pair of strings.
Number of Prefix Connected Groups Python/Java solution
The typical implementation iterates through the array, generates prefixes for each word, and checks them in a hash set. Python uses a set for O(1) membership checks, while Java uses HashSet. The same logic translates easily to C++, Go, and TypeScript.
How to solve Number of Prefix Connected Groups in O(n)?
Strict O(n) is not achievable because prefixes must be inspected character by character. The practical optimal solution is O(n * L). Iterate through the array, generate prefixes for each string, check them in a hash set, and increment the group count only when no prefix match exists.
What is the best approach for Number of Prefix Connected Groups?
The most efficient approach uses a hash table to track previously seen strings and detect prefix relationships. For each string, generate its prefixes and check whether any already exists in the set. If a prefix exists, the string belongs to that group; otherwise it forms a new group. This reduces redundant comparisons and runs in O(n * L) time.
Is Number of Prefix Connected Groups asked at Google/Amazon/Meta?
Prefix and string grouping problems appear frequently in interviews at companies like Google, Amazon, and Meta. While the exact problem title may vary, the underlying concepts—prefix detection, hashing, and string grouping—are common interview patterns.
What data structure is used in Number of Prefix Connected Groups?
A hash table (hash set or hash map) is the primary data structure. It allows constant-time prefix existence checks while scanning the list of strings. This structure avoids repeated pairwise comparisons between strings.
What is the time complexity of Number of Prefix Connected Groups?
The optimal hash table solution runs in O(n * L) time, where n is the number of strings and L is the maximum string length. Each string generates up to L prefixes, and each prefix check is an average O(1) hash lookup. Space complexity is O(n) for storing processed strings.

Ready to solve this problem?

Practice Number of Prefix Connected Groups with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays