How to count string num with limit memory?
Data Structures & Algorithms practice on Codemia
Step through 300 algorithm problems with animated visualisers that show the data structure changing as the code runs.
In modern computing, processing large datasets with limited resources is often a necessary challenge. Counting occurrences of strings efficiently while minimizing memory usage is a frequent task, especially in settings where hardware constraints are notable, such as IoT devices or embedded systems. This article explores strategies to efficiently count strings within memory limits.
Understanding the Problem
Counting strings typically involves reading through a dataset and maintaining a count for each unique string. The naive method would involve using a dictionary or hash map, which allows for quick updates and lookups. However, the memory footprint grows with the number of unique strings, potentially leading to issues in constrained environments.
Strategies for Counting with Limited Memory
1. Streaming Algorithms
Streaming algorithms process data in a single pass (or a few passes) and maintain a small, summary-like structure rather than the full dataset. These include:
- Count-Min Sketch: This is a probabilistic data structure that provides a frequency estimate for an item. Although it cannot guarantee exact counts, it offers significant memory savings.
- How It Works: It uses multiple hash functions to spread counts across a 2D array. For each input string, it increments counts in several locations determined by the hash functions. To approximate a count for a string, the minimum of these positions is taken as the estimate.
- Memory Usage: The size of the 2D array can be fixed based on desired accuracy, thus enabling predictable memory usage.
2. Bloom Filters
Bloom filters are another space-efficient probabilistic data structure used to check whether an element may be a member of a set. They provide quick membership tests but cannot support counting on their own. However, they are often used in conjunction with other methods to reduce data size.
3. Compression Techniques
Utilizing compression can also help in managing memory:
- Vocabulary Compression: Store unique strings in a compact form, using indexes or dictionaries that map to the actual string values. Only count indices rather than the full strings.
4. Bucket Count Method
This method involves dividing strings into a predetermined number of buckets based on a hash function and counting within each bucket. Although this is a simplistic approach, it can reduce memory requirements by leveraging fixed-size structures.
5. Frequency-Limited Counting
In certain scenarios, only the most frequent strings are of interest. Data structures like the Space-Saving algorithm or Heavy Hitters can help identify the most common strings without storing every string.
Example Implementation: Count-Min Sketch
Related reading
- How to count the frequency of the elements in an unordered list?
- How to create a distributed system that performs a task and come to a consensus of result?
- How to create a good evaluation function for a game?
- How to create an AVL Tree from ArrayList of values in On time?
- How to Create a nested index in MongoDB?
- How to create the most compact mapping n → isprimen up to a limit N?
- How to create cartesian product over arbitrary groups of numbers in Java?
- How to Deal with Algorithm/Data Structures Problems in Interview Process?

DSA Fundamentals
Master algorithmic patterns and data structures through hands-on LeetCode-style problems - from arrays and hashing to dynamic programming and advanced graphs.
View the courseTrack what you have practised
A free account saves your progress, solutions and study plan across every problem on Codemia.
Data Structures & Algorithms practice on Codemia
Step through 300 algorithm problems with animated visualisers that show the data structure changing as the code runs.