Want Help Cracking FAANG?

(Then click this)

 ×
Back to Question Bank

1805. Number of Different Integers in a String - Leetcode Solution

Code Implementation

import re
class Solution:
    def numDifferentIntegers(self, word: str) -> int:
        nums = re.findall(r'\d+', word)
        normalized = set(num.lstrip('0') or '0' for num in nums)
        return len(normalized)
      
#include <string>
#include <unordered_set>
using namespace std;

class Solution {
public:
    int numDifferentIntegers(string word) {
        unordered_set<string> s;
        int n = word.size();
        for (int i = 0; i < n; ) {
            if (isdigit(word[i])) {
                int j = i;
                while (j < n && isdigit(word[j])) ++j;
                string num = word.substr(i, j - i);
                // Remove leading zeros
                int k = 0;
                while (k < num.size() - 1 && num[k] == '0') ++k;
                s.insert(num.substr(k));
                i = j;
            } else {
                ++i;
            }
        }
        return s.size();
    }
};
      
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int numDifferentIntegers(String word) {
        Set<String> set = new HashSet<>();
        int n = word.length();
        int i = 0;
        while (i < n) {
            if (Character.isDigit(word.charAt(i))) {
                int j = i;
                while (j < n && Character.isDigit(word.charAt(j))) j++;
                String num = word.substring(i, j).replaceFirst("^0+", "");
                if (num.equals("")) num = "0";
                set.add(num);
                i = j;
            } else {
                i++;
            }
        }
        return set.size();
    }
}
      
var numDifferentIntegers = function(word) {
    let nums = word.match(/\d+/g);
    if (!nums) return 0;
    let set = new Set(nums.map(num => num.replace(/^0+/, '') || '0'));
    return set.size;
};

Problem Description

You are given a string word that contains both lowercase English letters and digits. Your task is to find out how many different integers are present in the string. An integer is defined as a contiguous sequence of digits (0-9) within the string. Leading zeros in an integer should be ignored when determining uniqueness (e.g., "001" and "1" are considered the same integer). Return the count of unique integers found in word.

Thought Process

At first glance, it seems we need to extract all groups of digits from the string and count how many unique numbers there are. The challenge is that numbers may have leading zeros, so "007" and "7" should be considered the same. Also, the string can have letters mixed in, so we must carefully separate digits from letters.

A brute-force approach might be to iterate through every character, collect digit sequences, normalize them by removing leading zeros, and then use a set to track unique numbers. However, we should also consider how to efficiently extract and normalize numbers, possibly using regular expressions or manual scanning.

Solution Approach

To solve the problem efficiently, we can follow these steps:
  • Step 1: Extract Numbers
    Iterate through the string and collect all contiguous sequences of digits. This can be done using regular expressions (e.g., \d+) or by manual iteration.
  • Step 2: Normalize Numbers
    For each number found, remove any leading zeros. If the number becomes an empty string (which happens if the number was all zeros), treat it as "0".
  • Step 3: Count Unique Numbers
    Store each normalized number in a set (or hash set) to ensure uniqueness. After processing the entire string, the size of the set is the answer.

We use a set because checking if an element exists and adding new elements are both fast operations (on average O(1) time).

Example Walkthrough

Let's walk through the string "a123bc34d8ef34":

  • We scan from left to right.
  • First, we find "123". Normalize: "123" (no leading zeros). Add to set: {"123"}.
  • Next, "34". Normalize: "34". Add to set: {"123", "34"}.
  • Then, "8". Normalize: "8". Add to set: {"123", "34", "8"}.
  • Finally, "34" again. Normalize: "34". Already in set, so no change.

The set contains {"123", "34", "8"}, so the answer is 3.

For input "a1b01c001":

  • Extracted numbers: "1", "01", "001"
  • Normalized: all become "1"
  • Set: {"1"}
The answer is 1.

Time and Space Complexity

  • Brute-force approach:
    If we used nested loops to compare every possible substring, it would be O(n^2), which is inefficient.
  • Optimized approach (used here):
    • Time Complexity: O(n), where n is the length of word. We scan the string once and perform constant-time operations for each character or number found.
    • Space Complexity: O(k*m), where k is the number of unique numbers and m is the average length of those numbers, since we store each unique normalized number in a set.

Summary

The key to this problem is accurately extracting and normalizing all digit sequences, then counting the unique ones. Using a set makes uniqueness checks efficient, and handling leading zeros ensures correct grouping. The solution is elegant because it leverages simple string processing and set operations for a linear-time answer.