Number of Different Integers in a String

Easy

#1651Time: 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.

Data structures

Hash Table String

Prompt

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

2 approaches with complexity analysis and trade-offs.

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.

Algorithm

Initialize a HashSet<String> 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.

Walkthrough

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.

1import java.util.HashSet;2import java.util.Set;3 4class Solution {5    public int numDifferentIntegers(String word) {6        // 1. Replace all non-digits with spaces.7        String processedWord = word.replaceAll("[a-z]", " ");8        9        // 2. Trim and split by one or more spaces.10        String[] numberStrings = processedWord.trim().split("\\s+");11        12        Set<String> uniqueIntegers = new HashSet<>();13        14        // Handle case where the string has no numbers.15        if (processedWord.trim().isEmpty()) {16            return 0;17        }18 19        // 3. Iterate, normalize, and add to set.20        for (String numStr : numberStrings) {21            // Find the first non-zero character to remove leading zeros.22            int i = 0;23            while (i < numStr.length() - 1 && numStr.charAt(i) == '0') {24                i++;25            }26            uniqueIntegers.add(numStr.substring(i));27        }28        29        // 4. Return the size of the set.30        return uniqueIntegers.size();31    }32}

Complexity

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.

Trade-offs

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.

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.

Algorithm

Initialize a HashSet<String> 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.

Walkthrough

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.

1import java.util.HashSet;2import java.util.Set;3 4class Solution {5    public int numDifferentIntegers(String word) {6        Set<String> uniqueIntegers = new HashSet<>();7        int n = word.length();8        int i = 0;9        while (i < n) {10            if (Character.isDigit(word.charAt(i))) {11                // Found the start of a number12                int j = i;13                // Find the end of the number segment14                while (j < n && Character.isDigit(word.charAt(j))) {15                    j++;16                }17                18                // Find the start of the number after skipping leading zeros19                int start = i;20                while (start < j - 1 && word.charAt(start) == '0') {21                    start++;22                }23                24                // Add the normalized number string to the set25                uniqueIntegers.add(word.substring(start, j));26                27                // Continue scanning from the end of the found number28                i = j;29            } else {30                // It's a letter, just move to the next character31                i++;32            }33        }34        return uniqueIntegers.size();35    }36}

Complexity

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.

Trade-offs

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.

Solutions

Solution

1class Solution {2public3  int numDifferentIntegers(String word) {4    Set<String> s = new HashSet<>();5    int n = word.length();6    for (int i = 0; i < n; ++i) {7      if (Character.isDigit(word.charAt(i))) {8        while (i < n && word.charAt(i) == '0') {9          ++i;10        }11        int j = i;12        while (j < n && Character.isDigit(word.charAt(j))) {13          ++j;14        }15        s.add(word.substring(i, j));16        i = j;17      }18    }19    return s.size();20  }21}

1class Solution {2public:3  int numDifferentIntegers(string word) {4    unordered_set<string> s;5    int n = word.size();6    for (int i = 0; i < n; ++i) {7      if (isdigit(word[i])) {8        while (i < n && word[i] == '0')9          ++i;10        int j = i;11        while (j < n && isdigit(word[j]))12          ++j;13        s.insert(word.substr(i, j - i));14        i = j;15      }16    }17    return s.size();18  }19};

1class Solution:2    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)

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem