Number of Different Integers in a String

Easy
520.

Number of Different Integers in a String

Number of Different Integers in a String is an easy coding problem on strings and hash table, asked in Amazon and Google interviews.

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 <= 1000
  • word consists of digits and lowercase English letters.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} word
 * @return {number}
 */
var numDifferentIntegers = function(word) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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 <= 1000
  • word consists of digits and lowercase English letters.

Hints for Number of Different Integers in a String

  1. Hint 1

    Scan for maximal digit runs rather than splitting on every letter.

  2. Hint 2

    Strip leading zeros before comparing — but a run of all zeros is the integer 0, not the empty string.

  3. 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

  1. Walk the string, skipping letters.
  2. On a digit, extend to the end of the maximal digit run.
  3. Strip leading zeros from the run; if nothing is left, use "0".
  4. Insert the normalised string into a set and continue after the run.
  5. 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/long overflows 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