Number of Different Integers in a String

Problem Description

So, you’ve stumbled upon a string filled with a delightful mix of letters and numbers, and you’re wondering, “How many different integers can I find in this chaotic mess?” Welcome to the world of the Number of Different Integers in a String problem! It’s like a treasure hunt, but instead of gold coins, you’re digging for unique integers hidden among the letters.

Imagine you’re at a party, and everyone is wearing name tags. Some people have the same name, but you want to count how many unique names are there. Now, replace names with integers, and you’ve got yourself a problem!

The task is to extract all the integers from a given string, ignore any leading zeros (because who needs those?), and count how many unique integers you can find.

Code Solution


class Solution:
    def numDifferentIntegers(self, word: str) -> int:
        nums = set()
        curr = []

        for c in word:
            if c.isdigit():
                curr.append(c)
            elif curr:
                nums.add(''.join(self._removeLeadingZeros(curr)))
                curr = []

        if curr:
            nums.add(''.join(self._removeLeadingZeros(curr)))

        return len(nums)

    def _removeLeadingZeros(self, s: str) -> str:
        index = next((i for i, c in enumerate(s) if c != '0'), -1)
        return ['0'] if index == -1 else s[index:]

Approach Explanation

The provided code solution takes a string as input and processes it character by character. It uses a set to store unique integers, ensuring that duplicates are automatically filtered out. When it encounters a digit, it collects it until a non-digit character is found. At that point, it converts the collected digits into an integer (after removing any leading zeros) and adds it to the set. Finally, it returns the size of the set, which represents the number of unique integers found.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(n), where n is the length of the input string. Each character is processed once.
Space Complexity	O(k), where k is the number of unique integers found. This is due to the storage in the set.

Real-World Example

Let’s say you’re a detective trying to crack a case. You find a note that says “I saw 007, 7, and 0007 at the park.” You need to report how many different numbers you saw. In this case, you’d realize that 007, 7, and 0007 all represent the same integer: 7. So, you’d report just one unique integer.