Number of Different Integers in a String - Practice Coding Problems

Number of Different Integers in a String - Problem

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.

Input & Output

Example 1 — Basic Case

$ Input: word = "a123bc34d8ef34"

› Output: 3

💡 Note: After replacing letters with spaces: " 123 34 8 34". The unique numbers are: "123", "34", "8". Note that "34" appears twice but counts as one unique number.

Example 2 — Leading Zeros

$ Input: word = "leet1234code234"

› Output: 2

💡 Note: After replacement: " 1234 234". The unique numbers are: "1234" and "234".

Example 3 — Leading Zeros Normalization

$ Input: word = "a1b01c001"

› Output: 1

💡 Note: After replacement: " 1 01 001". All three numbers normalize to "1" after removing leading zeros, so there's only 1 unique number.

Constraints

1 ≤ word.length ≤ 1000
word consists of digits and lowercase English letters.

Visualization

Tap to expand

Understanding the Visualization

Input Processing

String with mixed letters and digits

Number Extraction

Replace letters, extract and normalize numbers

Count Unique

Count distinct normalized integers

Key Takeaway

🎯 Key Insight: Use string processing to extract numbers, normalize them by removing leading zeros, then leverage a hash set for automatic duplicate removal and counting.

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is to extract numbers from the string and normalize them by removing leading zeros, then use a hash set for automatic deduplication. Best approach is the split and hash set method which cleanly separates string processing from uniqueness logic. Time: O(n), Space: O(k) where k is the number of unique integers.

Common Approaches

Approach	Time	Space	Notes
✓ Character-by-Character Parsing	O(n)	O(k)	Iterate through each character, build numbers manually, store in list and count unique
Split and Hash Set	O(n)	O(n)	Replace non-digits with spaces, split by spaces, normalize numbers, use set for uniqueness

Character-by-Character Parsing — Algorithm Steps

Iterate through each character
Build numbers character by character
Normalize by removing leading zeros
Store in list and count unique values

Visualization

Tap to expand

Step-by-Step Walkthrough

Scan Characters

Process each character, building numbers

Normalize Numbers

Remove leading zeros from extracted numbers

Count Unique

Use set to count distinct normalized numbers

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

#define MAX_NUMBERS 1000
#define MAX_NUM_LEN 100

int solution(char* word) {
    char numbers[MAX_NUMBERS][MAX_NUM_LEN];
    int count = 0;
    char currentNum[MAX_NUM_LEN] = "";
    int numLen = 0;
    
    for (int i = 0; word[i]; i++) {
        if (isdigit(word[i])) {
            currentNum[numLen++] = word[i];
        } else {
            if (numLen > 0) {
                currentNum[numLen] = '\0';
                // Remove leading zeros
                long long num = atoll(currentNum);
                sprintf(currentNum, "%lld", num);
                
                // Check if already exists
                int found = 0;
                for (int j = 0; j < count; j++) {
                    if (strcmp(numbers[j], currentNum) == 0) {
                        found = 1;
                        break;
                    }
                }
                if (!found) {
                    strcpy(numbers[count++], currentNum);
                }
                numLen = 0;
            }
        }
    }
    
    // Handle last number
    if (numLen > 0) {
        currentNum[numLen] = '\0';
        long long num = atoll(currentNum);
        sprintf(currentNum, "%lld", num);
        
        int found = 0;
        for (int j = 0; j < count; j++) {
            if (strcmp(numbers[j], currentNum) == 0) {
                found = 1;
                break;
            }
        }
        if (!found) {
            count++;
        }
    }
    
    return count;
}

int main() {
    char word[10000];
    fgets(word, sizeof(word), stdin);
    word[strcspn(word, "\n")] = 0;
    
    int result = solution(word);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through string of length n

✓ Linear Growth

Space Complexity

O(k)

Storage for k unique numbers extracted from string

✓ Linear Space

18.5K Views

Medium Frequency

~15 min Avg. Time

428 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Character-by-Character Parsing — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler