#1805

Easy

LeetCode Problem Workspace

Number of Different Integers in a String

Count all unique integers in a string by replacing letters and handling leading zeros correctly with a hash table approach.

hash table string

Problem Statement

You are given a string containing lowercase English letters and digits. Your task is to identify all integers embedded in the string and count how many distinct integer values exist.

To extract integers, replace every non-digit character with a space, split the string into separate number tokens, remove any leading zeros, and count only unique integers. For example, 'a123bc34d8ef34' becomes integers 123, 34, 8, and 34, and the distinct count is 3.

Examples

Example 1

Input: word = "a123bc34d8ef34"

Output: 3

The three different integers are "123", "34", and "8". Notice that "34" is only counted once.

Example 2

Input: word = "leet1234code234"

Output: 2

Example details omitted.

Example 3

Input: word = "a1b01c001"

Output: 1

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.

Solution Approach

Replace Non-Digit Characters

Scan the string and replace each letter with a space to isolate integer sequences. This simplifies parsing and ensures each number is separated properly for counting.

Use Hash Table for Uniqueness

Convert each extracted numeric substring to its integer value and insert it into a hash table (or set) to automatically remove duplicates and count only distinct integers.

Handle Leading Zeros

Before inserting into the hash table, strip leading zeros from each numeric substring. This avoids treating '01' and '1' as different numbers, which is a common error in this pattern.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) where n is the string length, as each character is processed once and inserting into a hash table is O(1) on average. Space complexity is O(k) for storing k unique integers in the hash table.

What Interviewers Usually Probe

Look for candidates using string parsing combined with a hash table.
Watch for handling of leading zeros as a subtle failure mode.
Expect a clean separation of letters and digits before counting unique numbers.

Common Pitfalls or Variants

Common pitfalls

Counting numeric substrings without removing leading zeros, causing duplicates to appear.
Using nested loops for comparison instead of a hash table, increasing complexity.
Failing to replace all non-digit characters, which can merge integers incorrectly.

Follow-up variants

Count distinct integers ignoring case-insensitive letters in a string.
Return both the unique integer count and the list of integers in sorted order.
Handle strings where integers are separated by multiple non-digit characters or punctuation.

FAQ

How do I handle leading zeros in this problem?

Convert each numeric substring to an integer or strip leading zeros before inserting into a set to ensure correct uniqueness counting.

Can I solve this without a hash table?

Yes, but it requires more complex comparison logic to check uniqueness manually, which is less efficient and prone to errors.

What is the main pattern used in Number of Different Integers in a String?

The key pattern is Hash Table plus String, focusing on parsing and deduplicating numeric substrings extracted from letters and digits.

Does splitting by non-digit characters always work?

Yes, as long as all non-digit characters are replaced with a consistent separator, splitting ensures each integer is isolated for counting.

What should I watch out for with large input strings?

Ensure that parsing and hash table insertion are linear in time and avoid unnecessary string copies to handle up to 1000 characters efficiently.

terminal

Solution

Solution 1: Double Pointers + Simulation

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

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

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)

Continue Practicing

#1807 evaluate the bracket pairs of a string #1796 second largest digit in a string #1790 check if one string swap can make strings equal