# Number of Different Integers in a String **Difficulty:** EASY [External](https://leetcode.com/problems/number-of-different-integers-in-a-string) Canonical: https://scaleengineer.com/dsa/problems/number-of-different-integers-in-a-string **Data structures:** Hash Table, String --- ## Problem 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 <= 1000` * `word` consists of digits and lowercase English letters. # Approaches ## Using Regular Expressions and a Set This approach leverages built-in string manipulation functions for a straightforward implementation. First, we use a regular expression to replace all non-digit characters with spaces. This effectively isolates the numbers within the string. Then, we split the resulting string by these spaces to obtain an array of individual number strings. Finally, we iterate through these strings, normalize them by removing any leading zeros, and add them to a `HashSet`. The set's nature of storing only unique elements allows us to easily find our answer by returning its final size. **Time:** O(N), where N is the length of the input string `word`. The `replaceAll`, `trim`, and `split` operations each take time proportional to the string length. The subsequent loop to process and store the numbers also takes O(N) in total, as the sum of the lengths of all number strings is at most N. · **Space:** O(N), where N is the length of the input string `word`. This space is used for the new string created by `replaceAll`, the array of strings from `split`, and the `HashSet`. In the worst case, all of these can be proportional to the input size. **Pros:** Conceptually simple and easy to implement using standard library functions.; The code is often more concise and readable for those familiar with regular expressions. **Cons:** Can be less efficient due to the overhead of regular expression processing.; Creates several intermediate data structures (a new string from `replaceAll` and an array from `split`), which can increase memory usage and have higher constant factors for time complexity. ### Explanation The core idea is to transform the input string into a format that is easy to parse. By replacing all letters with spaces, we get a string like `" 123 34 8 34"`. Splitting this by whitespace gives us the number candidates: `["123", "34", "8", "34"]`. The next crucial step is normalization. Since `"01"` and `"1"` represent the same integer, we must convert them to a canonical form before storing them. A simple way to do this is to remove all leading zeros. After normalizing each string, we add it to a `HashSet`. The set ensures that even though `"34"` appears twice, it's only stored once. The final count is simply the number of elements in the set. ```java import java.util.HashSet; import java.util.Set; class Solution { public int numDifferentIntegers(String word) { // 1. Replace all non-digits with spaces. String processedWord = word.replaceAll("[a-z]", " "); // 2. Trim and split by one or more spaces. String[] numberStrings = processedWord.trim().split("\\s+"); Set uniqueIntegers = new HashSet<>(); // Handle case where the string has no numbers. if (processedWord.trim().isEmpty()) { return 0; } // 3. Iterate, normalize, and add to set. for (String numStr : numberStrings) { // Find the first non-zero character to remove leading zeros. int i = 0; while (i < numStr.length() - 1 && numStr.charAt(i) == '0') { i++; } uniqueIntegers.add(numStr.substring(i)); } // 4. Return the size of the set. return uniqueIntegers.size(); } } ``` ### Algorithm * Initialize a `HashSet` to store unique numbers. * Use a regular expression like `[a-z]` to replace all lowercase letters in the input `word` with a space. This results in a new string where numbers are separated by spaces. * Trim any leading or trailing whitespace from the modified string to handle edge cases. * Split the string by one or more whitespace characters (`"\\s+"`) to get an array of strings. Each element in this array is a number represented as a string. * Iterate through this array of number strings. * For each non-empty string, normalize it by removing any leading zeros. For example, `"01"` and `"001"` both become `"1"`. A string of only zeros, like `"00"`, becomes `"0"`. * Add the normalized string to the `HashSet`. The set automatically handles duplicates. * Finally, the number of different integers is the size of the `HashSet`. ## Single Pass Iteration with a Set A more optimized approach is to iterate through the string just once, character by character. We can use pointers or indices to identify numeric segments directly from the input string without creating large intermediate copies. As we find each number, we extract it, normalize it by removing leading zeros, and add the canonical form to a `HashSet`. This method avoids the overhead associated with regular expressions and creating intermediate data structures, making it more efficient in terms of both memory and speed. **Time:** O(N), where N is the length of the input string `word`. We iterate through the string with the main pointer `i`. The inner loops also advance pointers (`j`, `start`) over segments of the string. Each character of the string is visited only a constant number of times. The total time for all substring operations and set insertions is O(N). · **Space:** O(N), where N is the length of the input string. The space is dominated by the `HashSet`. In the worst-case scenario (e.g., '1a2a3a...'), the set could store O(N) distinct strings, with a total character count proportional to N. **Pros:** More efficient in terms of both time and space as it avoids creating large intermediate data structures like new strings and arrays.; Processes the string in a single pass, leading to better performance with lower constant factors, especially for large inputs. **Cons:** The implementation is slightly more complex, requiring manual pointer management to identify and process numbers.; The code might be less immediately obvious to read compared to the high-level regex-based solution. ### Explanation This approach manually parses the string. We iterate with a primary pointer `i`. When `word.charAt(i)` is a digit, we know we've started a number. We then use a secondary pointer `j` to find where this sequence of digits ends. The substring `word.substring(i, j)` gives us the number. We then perform normalization in-place on these indices. We advance a `start` pointer from `i` forward as long as we see leading zeros (while ensuring we don't consume the entire number if it's just `"0"`). The substring from `start` to `j` is the canonical representation, which we add to our set. After processing a number, we set `i = j` to avoid re-scanning the same digits and continue our single pass through the string. ```java import java.util.HashSet; import java.util.Set; class Solution { public int numDifferentIntegers(String word) { Set uniqueIntegers = new HashSet<>(); int n = word.length(); int i = 0; while (i < n) { if (Character.isDigit(word.charAt(i))) { // Found the start of a number int j = i; // Find the end of the number segment while (j < n && Character.isDigit(word.charAt(j))) { j++; } // Find the start of the number after skipping leading zeros int start = i; while (start < j - 1 && word.charAt(start) == '0') { start++; } // Add the normalized number string to the set uniqueIntegers.add(word.substring(start, j)); // Continue scanning from the end of the found number i = j; } else { // It's a letter, just move to the next character i++; } } return uniqueIntegers.size(); } } ``` ### Algorithm * Initialize a `HashSet` to store the unique normalized integers. * Initialize a pointer `i = 0` to traverse the string `word` from left to right. * Loop while `i` is less than the length of `word`: * If the character at `i` is a letter, it's a separator. Simply increment `i` and continue to the next character. * If the character at `i` is a digit, it marks the beginning of a number. * Use a second pointer `j`, starting from `i`, to find the end of the contiguous block of digits. Keep incrementing `j` as long as it's within bounds and points to a digit. * The substring from `i` to `j-1` is our number string. * To handle leading zeros, find the index of the first non-zero digit in this substring. Let's call this index `start`. * The normalized number is the substring from `start` to `j`. * Add this normalized string to the `HashSet`. * Crucially, update the main pointer `i` to `j` to continue scanning from the character immediately after the number we just processed. * Return the final size of the `HashSet`. # Solutions ### Java ```java class Solution { public int numDifferentIntegers(String word) { Set s = new HashSet<>(); int n = word.length(); for (int i = 0; i < n; ++i) { if (Character.isDigit(word.charAt(i))) { while (i < n && word.charAt(i) == '0') { ++i; } int j = i; while (j < n && Character.isDigit(word.charAt(j))) { ++j; } s.add(word.substring(i, j)); i = j; } } return s.size(); } } ``` ### CPP ```cpp class Solution { public: int numDifferentIntegers(string word) { unordered_set s; int n = word.size(); for (int i = 0; i < n; ++i) { if (isdigit(word[i])) { while (i < n && word[i] == '0') ++i; int j = i; while (j < n && isdigit(word[j])) ++j; s.insert(word.substr(i, j - i)); i = j; } } return s.size(); } }; ``` ### Python ```python class Solution: def numDifferentIntegers(self, word: str) -> int: s = set() i, n = 0, len(word) while i < n: if word[i]. isdigit(): while i < n and word[i] == '0': i += 1 j = i while j < n and word[j]. isdigit(): j += 1 s . add(word[i: j]) i = j i += 1 return len(s) ```