Number of Different Integers in a String — Solution
Number of Different Integers in a String solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Number of Different Integers in a String is an easy coding problem on strings and hash table, asked in Amazon and Google interviews.
- Difficulty: Easy
- Topics: Strings, Hash Table
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given a string word of digits and lowercase letters. Replace every maximal run of letters with a single space, then read off the integers that remain.
Return how many different integers appear. Leading zeros are ignored, so "01" and "1" are the same integer.
Example 1
Input: word = "a123bc34d8ef34"
Output: 3
Explanation: The integers are 123, 34, 8 and 34 — three distinct values.
Example 2
Input: word = "leet1234code234"
Output: 2
Example 3
Input: word = "a1b01c001"
Output: 1
Explanation: All three are the integer 1.
Constraints
1 <= word.length <= 1000word consists of digits and lowercase English letters.
Hints for Number of Different Integers in a String
Hint 1
Scan for maximal digit runs rather than splitting on every letter.
Hint 2
Strip leading zeros before comparing — but a run of all zeros is the integer 0, not the empty string.
Hint 3
The numbers may be far too large for a 64-bit integer, so compare them as normalised strings.
How to solve Number of Different Integers in a String
The integers can be up to 1000 digits long, so they must be compared as strings. Normalising each digit run by stripping leading zeros makes string equality agree with numeric equality.
Approach
- Walk the string, skipping letters.
- On a digit, extend to the end of the maximal digit run.
- Strip leading zeros from the run; if nothing is left, use
"0". - Insert the normalised string into a set and continue after the run.
- Return the set's size.
Why it works
Two digit runs denote the same integer exactly when they agree after leading zeros are removed, so normalised-string equality is precisely numeric equality — without ever needing a numeric type.
Complexity
- Time —
O(n) - Space —
O(n)
Pitfalls
- Parsing to
int/longoverflows on runs longer than about 19 digits. - Stripping every zero rather than only the leading ones turns
"100"into"1". - A run of all zeros normalises to
"0", not to the empty string.
Reference solution
Python
def numDifferentIntegers(word: str) -> int:
seen = set()
i = 0
n = len(word)
while i < n:
if word[i].isdigit():
j = i
while j < n and word[j].isdigit():
j += 1
t = word[i:j].lstrip('0')
seen.add(t if t else '0')
i = j
else:
i += 1
return len(seen)Java
public static int numDifferentIntegers(String word) {
HashSet<String> seen = new HashSet<>();
int i = 0, n = word.length();
while (i < n) {
char c = word.charAt(i);
if (c >= '0' && c <= '9') {
int j = i;
while (j < n && word.charAt(j) >= '0' && word.charAt(j) <= '9') j++;
int k = i;
while (k < j - 1 && word.charAt(k) == '0') k++;
seen.add(word.substring(k, j));
i = j;
} else {
i++;
}
}
return seen.size();
}C++
int numDifferentIntegers(string word) {
unordered_set<string> seen;
int i = 0, n = (int) word.size();
while (i < n) {
if (word[i] >= '0' && word[i] <= '9') {
int j = i;
while (j < n && word[j] >= '0' && word[j] <= '9') j++;
int k = i;
while (k < j - 1 && word[k] == '0') k++;
seen.insert(word.substr(k, j - k));
i = j;
} else {
i++;
}
}
return (int) seen.size();
}JavaScript
var numDifferentIntegers = function(word) {
const seen = {};
let i = 0;
while (i < word.length) {
const c = word.charAt(i);
if (c >= "0" && c <= "9") {
let j = i;
while (j < word.length && word.charAt(j) >= "0" && word.charAt(j) <= "9") j++;
let t = word.slice(i, j);
let k = 0;
while (k < t.length - 1 && t.charAt(k) === "0") k++;
t = t.slice(k);
if (t === "") t = "0";
seen[t] = true;
i = j;
} else {
i++;
}
}
return Object.keys(seen).length;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Hashing: Hash Maps and Hash Sets