algoadvance

Leetcode 1805. Number of Different Integers in a String

Problem Statement:

Given a string word composed of digits and lowercase English letters, you need to find the number of different integers in the string. An integer is a contiguous sequence of digits, which may not have leading zeros.

Example:

• Example 1:
  • Input: word = "a123bc34d8ef34"
  • Output: 3
  • Explanation: The integers found in the word are “123”, “34”, “8”, and “34”. The different integers are “123”, “34”, and “8”.
• Example 2:
  • Input: word = "leet1234code234"
  • Output: 2
  • Explanation: The integers found in the word are “1234” and “234”. The different integers are “1234” and “234”.

Clarifying Questions:

1. Should numbers be considered only if they are contiguous?
   • Yes, only contiguous sequences of digits should be considered as integers.
2. Can leading zeros be disregarded when comparing two numbers?
   • Yes, leading zeros should be ignored when determining if two numbers are the same.
3. Are there any constraints on the string length?
   • Yes, according to LeetCode’s typical constraints, the string length should be manageable within usual competitive programming limits (up to (10^5) characters).

Strategy:

1. Traverse the string to extract all contiguous subsequences of digits.
2. Use a set to store these integers in string form (while stripping leading zeros).
3. The size of the set at the end will represent the number of distinct integers.

Code Implementation:

#include <iostream>
#include <unordered_set>
#include <string>
using namespace std;

int numDifferentIntegers(string word) {
    unordered_set<string> uniqueIntegers;
    int n = word.length();
    string currentNumber = "";

    for (int i = 0; i < n; ++i) {
        if (isdigit(word[i])) {
            currentNumber += word[i];
        } else {
            if (!currentNumber.empty()) {
                // Remove leading zeros
                int index = 0;
                while (index < currentNumber.length() && currentNumber[index] == '0') {
                    ++index;
                }
                string cleanNumber = currentNumber.substr(index);
                if (cleanNumber.empty()) {
                    cleanNumber = "0";
                }
                uniqueIntegers.insert(cleanNumber);
                currentNumber = "";
            }
        }
    }
    
    // Check if there's a number left at the end of the string
    if (!currentNumber.empty()) {
        int index = 0;
        while (index < currentNumber.length() && currentNumber[index] == '0') {
            ++index;
        }
        string cleanNumber = currentNumber.substr(index);
        if (cleanNumber.empty()) {
            cleanNumber = "0";
        }
        uniqueIntegers.insert(cleanNumber);
    }
    
    return uniqueIntegers.size();
}

int main() {
    string word;
    cin >> word;
    cout << numDifferentIntegers(word) << endl;
    return 0;
}

Time Complexity:

• Time Complexity: (O(n)), where (n) is the length of the input string word. We traverse the string once and perform operations of string cleaning, insertion into a set, and comparison, which are all (O(1)) on average per character due to the underlying hash table operations in the set.
• Space Complexity: (O(m)), where (m) is the number of distinct integers (with ignoring the leading zeros), as we store each distinct cleaned number in the set. This typically is less than (n), assuming typical input conditions.

This solution efficiently identifies and counts the distinct integers within the input string.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• 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?