You are given a string word that consists of digits and lowercase English letters.
You will replace every non-digit character with a space. For example, "a123bc34d8ef34" will become " 123 34 8 34". Notice that you are left with some integers that are separated by at least one space: "123", "34", "8", and "34".
Return the number of different integers after performing the replacement operations on word.
Two integers are considered different if their decimal representations without any leading zeros are different.
Example 1:
Input: word = "a123bc34d8ef34" Output: 3 Explanation: The three different integers are "123", "34", and "8". Notice that "34" is only counted once.
Example 2:
Input: word = "leet1234code234" Output: 2
Example 3:
Input: word = "a1b01c001" Output: 1 Explanation: The three integers "1", "01", and "001" all represent the same integer because the leading zeros are ignored when comparing their decimal values.
Constraints:
1 <= word.length <= 1000word consists of digits and lowercase English letters.Problem Overview: You receive a string containing lowercase letters and digits. Every continuous sequence of digits represents an integer. The task is to count how many distinct integers appear in the string. Leading zeros should not create separate values, so "001" and "1" represent the same integer.
Approach 1: String Manipulation and Set Storage (Time: O(n), Space: O(n))
Scan the string once and extract every contiguous sequence of digits. Each sequence represents a number. Before storing it, normalize the value by removing leading zeros so equivalent numbers map to the same representation. Insert the normalized number into a set (hash table). Because sets automatically remove duplicates, the final answer is simply the size of the set. This approach works well because hash lookups and insertions run in average O(1), making the entire scan linear. The solution heavily relies on string parsing and a hash table to track uniqueness.
Approach 2: Two-Pointer Sliding Window (Time: O(n), Space: O(n))
Instead of building numbers character-by-character, use two pointers to mark the start and end of each numeric segment. Move the right pointer across the string. When a digit is found, expand the window until a non-digit appears. The substring between the pointers represents one integer. Strip leading zeros and insert the normalized value into a set. Then continue scanning from the next position. This pattern mirrors the classic two pointers technique where a window isolates relevant substrings. It improves readability when dealing with grouped characters and avoids repeated digit checks inside loops.
Recommended for interviews: The string parsing with a hash set is what most interviewers expect. It shows you can iterate through a string, correctly extract numeric segments, normalize values, and use a hash-based data structure to enforce uniqueness. The two-pointer variation expresses the same idea with clearer boundary control. Demonstrating both shows strong understanding of string processing patterns.
One straightforward approach to solve this problem is to iterate through the string, replace all non-digit characters with a space, and then split the string into words using space as a delimiter.
Once the words are split, they are cleaned from leading zeros, and added to a set since we are interested in unique integers only.
The size of the set, therefore, will be the result because it contains only unique integers extracted from the original string.
The C code replaces non-digit characters with spaces, then uses strtok to tokenize the string by spaces.
The tokenized integer strings are cleaned of leading zeros and stored in an array. Each integer string is compared to existing entries to ensure uniqueness, hence defining a "set-like" behavior.
Time Complexity: O(n * m), where n is the number of characters in the string, and m is the average length of the tokens (since strcmp may run m times).
Space Complexity: O(n), with n being the number of unique integer tokens.
This approach uses two indices to maintain a window (or segment) of the current potential integer being examined. This is a manual implementation distinct from tokenization, aiming to extract numbers directly from traversal.
As soon as a 'finished' integer is identified, it is inserted into a set after removing leading zeros from the number formed within that window.
This method is particularly effective in traversal-centric models where tokenization is costlier.
The C implementation uses a set of character arrays to track unique numbers in-place. Starting and finishing indices determine the exact positioning of an integer in the string, which is compared across detected entries before recording.
Time Complexity: O(n * m), where n is the string length, and m stands for average substring length checks made for duplication.
Space Complexity: O(n), where n is a measure of unique integers derived before removal of duplications.
Traverse the string word, find the start and end positions of each integer, cut out this substring, and store it in the hash set s.
After the traversal, return the size of the hash set s.
Note, the integer represented by each substring may be very large, we cannot directly convert it to an integer. Therefore, we can remove the leading zeros of each substring before storing it in the hash set.
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the string word.
| Approach | Complexity |
|---|---|
| String Manipulation and Set Storage | Time Complexity: O(n * m), where n is the number of characters in the string, and m is the average length of the tokens (since strcmp may run m times). |
| Two-Pointer Sliding Window | Time Complexity: O(n * m), where n is the string length, and m stands for average substring length checks made for duplication. |
| Double Pointers + Simulation | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| String Manipulation and Set Storage | O(n) | O(n) | General case. Simple implementation when extracting numbers directly from the string. |
| Two-Pointer Sliding Window | O(n) | O(n) | Useful when treating digit sequences as windows or when extending to substring-based problems. |
1805. Number of Different Integers in a String (Leetcode Easy) • Programming Live with Larry • 827 views views
Watch 9 more video solutions →Practice Number of Different Integers in a String with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor