algoadvance

You are provided with a string word that consists of digits and lowercase English letters. You need to return the number of distinct integers present in the word. An integer is a contiguous sequence of digits within the string. Leading zeros are ignored when determining distinct integers.

Example 1:

Input: word = "a123bc34d8ef34"
Output: 3
Explanation: The integers found in the string are "123", "34", "8", and "34". 
The distinct integers are "123", "34", and "8".

Example 2:

Input: word = "leet1234code234"
Output: 2
Explanation: The integers found in the string are "1234" and "234".

Example 3:

Input: word = "a1b01c001"
Output: 1
Explanation: The integers found in the string are "1", "01", and "001". 
The distinct integers when leading zeros are ignored are all "1".

Clarifying Questions

1. Q: Can the string contain any non-digit, non-lowercase characters (e.g., special characters)? A: No, the problem specifies the string contains only digits and lowercase English letters.

2. Q: What should be returned if there are no digits in the string? A: If there are no digits in the string, the function should return 0 as there are no integers present.

Strategy

1. Extract integers: Traverse the string to extract all contiguous sequences of digits.
2. Normalize integers: Convert these sequences into integers to ignore leading zeros.
3. Count distinct integers: Use a set to collect unique integers and return the size of this set.

Code

def numDifferentIntegers(word: str) -> int:
    import re
    
    # Use regex to find all contiguous sequences of digits
    digit_sequences = re.findall(r'\d+', word)
    
    # Convert sequences to integers to ignore leading zeros
    unique_integers = {int(seq) for seq in digit_sequences}
    
    # Return the number of unique integers
    return len(unique_integers)

# Example usage:
# print(numDifferentIntegers("a123bc34d8ef34"))  # Output: 3
# print(numDifferentIntegers("leet1234code234"))  # Output: 2
# print(numDifferentIntegers("a1b01c001"))       # Output: 1

Time Complexity

• Extraction of sequences: The regex operation re.findall(r'\d+', word) scans the string once, which is O(n), where n is the length of the string.
• Normalization and uniqueness: Creating a set from the extracted sequences involves converting each sequence to an integer and inserting into the set. The time complexity of this process is also O(n) assuming a small number of distinct sequences relative to the length of the string.

Overall, the time complexity is O(n), where n is the length of the string. This ensures the solution is efficient even for relatively long strings.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?