Find Trending Hashtags - Solution & Explanation

Problem Overview: You are given tweet text that may contain hashtags (words starting with #). The task is to extract those hashtags, count how often each appears, and return the ones that are trending based on frequency.

Approach 1: Extract Substring + Grouping (O(n * m) time, O(k) space)

Scan each tweet and extract every token that starts with #. In SQL, this typically uses string functions or regex to isolate hashtags, followed by GROUP BY to count occurrences. In Python, split the tweet text into tokens, filter tokens beginning with #, and increment counts in a dictionary. The key insight is that trending hashtags are simply the most frequent ones after normalizing and aggregating all hashtag occurrences.

After extraction, aggregate using a hash-based structure such as a dictionary or SQL grouping. Each unique hashtag becomes a key, and every occurrence increments its frequency. Finally, sort the results by frequency in descending order (and lexicographically if ties are required). This approach processes every tweet once and performs constant‑time updates per hashtag.

This pattern appears frequently in database aggregation problems and text processing tasks. The extraction step is essentially a string parsing problem, while the counting step relies on hash-based grouping similar to a hash map frequency table.

Approach 2: Regex Extraction + Frequency Map (O(n * m) time, O(k) space)

Instead of manually splitting tokens, use a regular expression such as #\w+ to directly extract hashtags from each tweet. Regex engines scan the string and return all matches, which are then aggregated in a frequency map or grouped in SQL. This reduces edge cases when punctuation or mixed formatting appears in the tweet text.

The counting and sorting steps remain identical. Each extracted hashtag increments its counter, and the final list is ordered by descending frequency. Regex-based extraction is often cleaner in Python and many SQL engines that support REGEXP_SUBSTR or similar functions.

Recommended for interviews: The substring extraction plus grouping approach is what interviewers expect. It shows you understand how to parse structured tokens from text and aggregate them efficiently. A simple brute-force scan demonstrates the core idea, but the optimal solution uses hash-based counting or SQL GROUP BY to compute frequencies in linear time relative to the input size.