Counting the Number of Different Integers in a String


You are given a string word that consists of digits and lowercase English letters. You will replace every non-digit character with a space. For example, “a123bc34d8ef34″ will become ” 123 34 8 34″. Notice that you are left with some integers that are separated by at least one space: “123”, “34”, “8”, and “34”.

Return the number of different integers after performing the replacement operations on word. Two integers are considered different if their decimal representations without any leading zeros are different.

Example 1:
Input: word = “a123bc34d8ef34”
Output: 3
Explanation: The three different integers are “123”, “34”, and “8”. Notice that “34” is only counted once.

Example 2:
Input: word = “leet1234code234”
Output: 2

Example 3:
Input: word = “a1b01c001”
Output: 1
Explanation: 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.

Hints:
Try to split the string so that each integer is in a different string.
Try to remove each integer’s leading zeroes and compare the strings to find how many of them are unique.

Algorithm to Compute the Number of Different Integers in a String

We have to deal with so many edge/special test cases. However, we can iterate through the string and replace non-digit with a space. Since the string in Python is immutable, we can construct a new string.

Finally, we split the string by spaces, and map converting to integer which ignores the leading zeros. Finally, we count the number of the elements in the set.

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def numDifferentIntegers(self, word: str) -> int:
        if len(word) == 0:
            return 0
        a = set()
        s = ""
        for i in word:
            if i.isdigit():
                s += i
            else:
                s += " "
        return len(set(map(int, s.split())))
class Solution:
    def numDifferentIntegers(self, word: str) -> int:
        if len(word) == 0:
            return 0
        a = set()
        s = ""
        for i in word:
            if i.isdigit():
                s += i
            else:
                s += " "
        return len(set(map(int, s.split())))

The time complexity is O(N) where N is the number of the characters in the given string. And space complexity is O(N) becauswe we are using a set to store the unique numbers. This is also assuming that the string concatenation in Python is O(1) constant time. We can also use the list/array to append the characters.

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
loading...
460 words
Last Post: Teaching Kids Programming - Algorithms to Find Center of Star Graph
Next Post: Teaching Kids Programming - Breadth First Search Algorithm to Find the Only Child in Binary Tree

The Permanent URL is: Counting the Number of Different Integers in a String

Leave a Reply