Number of Different Integers in a String

Difficulty: Easy | Acceptance: 40.30% | Paid: No Topics: Hash Table, String

You are given a string word that consists of digits and lowercase English letters.

You must replace every non-digit character of the string with a space.

For example, “a123bc34d8ef34” becomes ” 123 34 8 34”.

Return the number of different integers that appear in word after the replacement.

Note that leading zeros are ignored.

For example, “01” and “001” represent the same integer “1”.

• Examples
• Constraints
• Regex Extraction
• Iterative Parsing
• String Split

Examples

Input: word = "a123bc34d8ef34"
Output: 3
Explanation: The three different integers are "123", "34", and "8". Note that "34" is counted only once.

Input: word = "leet1234code234"
Output: 2

Input: word = "a1b01c001"
Output: 1
Explanation: The three integers "1", "01", and "001" all represent the same integer "1".

Constraints

1 <= word.length <= 1000
word consists of digits and lowercase English letters.

Regex Extraction

Intuition Use regular expressions to find all digit sequences, then normalize each by removing leading zeros before adding to a set.

Steps

• Use regex pattern \d+ to find all consecutive digit sequences
• For each match, strip leading zeros (keeping at least one digit)
• Add normalized string to a hash set
• Return the size of the set

import re

class Solution:
    def numDifferentIntegers(self, word: str) -> int:
        numbers = re.findall(r'd+', word)
        unique = set()
        for num in numbers:
            stripped = num.lstrip('0')
            if stripped == '':
                stripped = '0'
            unique.add(stripped)
        return len(unique)

Complexity

• Time: O(n) where n is the length of the string
• Space: O(n) for storing unique numbers
• Notes: Clean and concise, regex handles the heavy lifting

Iterative Parsing

Intuition Scan through the string character by character, collecting consecutive digits into numbers and normalizing them.

Steps

• Iterate through the string with index i
• When a digit is found, extend j to capture all consecutive digits
• Extract substring, strip leading zeros, add to set
• Skip non-digit characters

class Solution:
    def numDifferentIntegers(self, word: str) -> int:
        unique = set()
        i = 0
        n = len(word)
        
        while i < n:
            if word[i].isdigit():
                j = i
                while j < n and word[j].isdigit():
                    j += 1
                num = word[i:j]
                stripped = num.lstrip('0')
                if stripped == '':
                    stripped = '0'
                unique.add(stripped)
                i = j
            else:
                i += 1
        
        return len(unique)

Complexity

• Time: O(n) single pass through the string
• Space: O(n) for storing unique numbers
• Notes: No regex dependency, explicit control over parsing

String Split

Intuition Replace all letters with spaces, then split by whitespace to isolate numbers for normalization.

Steps

• Replace all alphabetic characters with spaces
• Split the resulting string by whitespace
• Process each non-empty token by stripping leading zeros
• Add to set and return count

import re

class Solution:
    def numDifferentIntegers(self, word: str) -> int:
        parts = re.split('[a-z]+', word)
        unique = set()
        
        for part in parts:
            if part:
                stripped = part.lstrip('0')
                if stripped == '':
                    stripped = '0'
                unique.add(stripped)
        
        return len(unique)

Complexity

• Time: O(n) for string transformation and splitting
• Space: O(n) for the transformed string and set
• Notes: Intuitive approach following the problem description literally