Number of Different Integers in a String solution and explanation
9 more videos on this problem
1805. Number of Different Integers in a String (Leetcode Easy)Programming Live with Larry · 6:23 · 829 views
1805. Number of Different Integers in a String | leetcode || C++HDcode · 9:19 · 509 views
Weekly Contest 234 Q1 Number of Different Integers in a StringCoding Ninjas Webinars and Contest Editorials · 7:32 · 474 views
Leetcode 1805 Number of Different Integers in a String (without regex)Bborian · 5:57 · 259 views
Number of Different Integers in a String #leetCode #Strings #java #javaInterview #interviewQuestionsCodeVia · 8:43 · 145 views
1805 number of different integers in a string on leetcode #coding #amazon #leetcode #python #javaManasa Duggempudi Academy · 8:19 · 126 views
Number of Different Integers in a String (LeetCode) Weekly Contest 234 C++ codeHrushikesh Patil · 3:49 · 93 views
1805. Number of Different Integers in a String - JavaScript - 1 LineAlgoPrepMaster · 1:09 · 29 views
Day 609: LeetCode Problem 1805. Number of Different Integers in a String -SwiftiOSxBank · 9:18 · 22 views
Number of Different Integers in a String - Leetcode python coding by ElrikCoding and Math for kids with Jake · 2:50 · 14 views
The 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.
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 <= 1000wordconsists of digits and lowercase English letters.
Approach overview
Problem Overview: You receive a string containing lowercase letters and digits. Every continuous sequence of digits represents an integer. The task is to count how many distinct integers appear in the string. Leading zeros should not create separate values, so "001" and "1" represent the same integer.
Approach 1: String Manipulation and Set Storage (Time: O(n), Space: O(n))
Scan the string once and extract every contiguous sequence of digits. Each sequence represents a number. Before storing it, normalize the value by removing leading zeros so equivalent numbers map to the same representation. Insert the normalized number into a set (hash table). Because sets automatically remove duplicates, the final answer is simply the size of the set. This approach works well because hash lookups and insertions run in average O(1), making the entire scan linear. The solution heavily relies on string parsing and a hash table to track uniqueness.
Approach 2: Two-Pointer Sliding Window (Time: O(n), Space: O(n))
Instead of building numbers character-by-character, use two pointers to mark the start and end of each numeric segment. Move the right pointer across the string. When a digit is found, expand the window until a non-digit appears. The substring between the pointers represents one integer. Strip leading zeros and insert the normalized value into a set. Then continue scanning from the next position. This pattern mirrors the classic two pointers technique where a window isolates relevant substrings. It improves readability when dealing with grouped characters and avoids repeated digit checks inside loops.
Recommended for interviews: The string parsing with a hash set is what most interviewers expect. It shows you can iterate through a string, correctly extract numeric segments, normalize values, and use a hash-based data structure to enforce uniqueness. The two-pointer variation expresses the same idea with clearer boundary control. Demonstrating both shows strong understanding of string processing patterns.
Approach 1: String Manipulation and Set Storage
One straightforward approach to solve this problem is to iterate through the string, replace all non-digit characters with a space, and then split the string into words using space as a delimiter.
Once the words are split, they are cleaned from leading zeros, and added to a set since we are interested in unique integers only.
The size of the set, therefore, will be the result because it contains only unique integers extracted from the original string.
def numDifferentIntegers(word: str) -> int:
import re
tokens = re.split('[a-z]+', word)
unique_numbers = {int(token.lstrip('0') or '0') for token in tokens if token}
return len(unique_numbers)
print(numDifferentIntegers("a123bc34d8ef34"))import java.util.HashSet;
public class Main {
public static int numDifferentIntegers(String word) {
StringBuilder modWord = new StringBuilder();
for (char c : word.toCharArray()) {
if (Character.isDigit(c)) modWord.append(c);
else modWord.append(' ');
}
HashSet<String> uniqueNumbers = new HashSet<>();
for (String token : modWord.toString().split(" ")) {
if (token.length() > 0) {
token = token.replaceAll("^0+", "");
uniqueNumbers.add(token);
}
}
return uniqueNumbers.size();
}
public static void main(String[] args) {
String word = "a123bc34d8ef34";
System.out.println(numDifferentIntegers(word));
}
}#include <iostream>
#include <sstream>
#include <unordered_set>
#include <string>
#include <cctype>
int numDifferentIntegers(std::string word) {
for (char &ch : word) {
if (isalpha(ch)) ch = ' ';
}
std::stringstream ss(word);
std::string token;
std::unordered_set<std::string> uniqueNumbers;
while (ss >> token) {
while (token.length() > 1 && token[0] == '0') {
token.erase(token.begin());
}
uniqueNumbers.insert(token);
}
return uniqueNumbers.size();
}
int main() {
std::string word = "a123bc34d8ef34";
std::cout << numDifferentIntegers(word) << std::endl;
return 0;
}function numDifferentIntegers(word) {
const tokens = word.split(/\D+/);
const uniqueNumbers = new Set();
for (let token of tokens) {
if (token.length > 0) {
uniqueNumbers.add(BigInt(token).toString());
}
}
return uniqueNumbers.size;
}
console.log(numDifferentIntegers("a123bc34d8ef34"));#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
int numDifferentIntegers(char * word) {
char modWord[1001] = {0};
int len = strlen(word);
int j = 0;
for (int i = 0; i < len; i++) {
if (isdigit(word[i])) {
modWord[j++] = word[i];
} else {
modWord[j++] = ' ';
}
}
char *token = strtok(modWord, " ");
char *unique[1000] = {NULL};
int uniqueCount = 0;
while (token != NULL) {
while (*token == '0') token++;
int found = 0;
for (int i = 0; i < uniqueCount; i++) {
if (strcmp(unique[i], token) == 0) {
found = 1;
break;
}
}
if (!found) {
unique[uniqueCount++] = strdup(token);
}
token = strtok(NULL, " ");
}
for (int i = 0; i < uniqueCount; i++) {
free(unique[i]);
}
return uniqueCount;
}
int main() {
char word[] = "a123bc34d8ef34";
printf("%d\n", numDifferentIntegers(word));
return 0;
}using System;
using System.Collections.Generic;
public class Solution {
public int NumDifferentIntegers(string word) {
var modWord = new System.Text.StringBuilder();
foreach (char c in word) {
if (char.IsDigit(c)) modWord.Append(c);
else modWord.Append(' ');
}
var uniqueNumbers = new HashSet<string>();
foreach (var token in modWord.ToString().Split(new[] { ' ' }, StringSplitOptions.RemoveEmptyEntries)) {
var cleanToken = token.TrimStart('0');
if (cleanToken == "") cleanToken = "0";
uniqueNumbers.Add(cleanToken);
}
return uniqueNumbers.Count;
}
public static void Main() {
Solution sol = new Solution();
Console.WriteLine(sol.NumDifferentIntegers("a123bc34d8ef34"));
}
}The Python implementation uses regular expressions to split the input string by non-digit characters directly.
A set comprehension is used to ensure each discovered integer, with leading zeros removed, is stored uniquely.
Time Complexity: O(n), primarily decided by the length of the string and number of tokens.
Space Complexity: O(k), where k accounts for the unique numbers stored in the set.
Approach 2: Two-Pointer Sliding Window
This approach uses two indices to maintain a window (or segment) of the current potential integer being examined. This is a manual implementation distinct from tokenization, aiming to extract numbers directly from traversal.
As soon as a 'finished' integer is identified, it is inserted into a set after removing leading zeros from the number formed within that window.
This method is particularly effective in traversal-centric models where tokenization is costlier.
def numDifferentIntegers(word: str) -> int:
num_set = set()
i = 0
n = len(word)
while i < n:
if word[i].isdigit():
j = i
while j < n and word[j].isdigit():
j += 1
num = word[i:j].lstrip('0') or '0'
num_set.add(num)
i = j
else:
i += 1
return len(num_set)
print(numDifferentIntegers("a123bc34d8ef34"))import java.util.HashSet;
public class Main {
public static int numDifferentIntegers(String word) {
HashSet<String> uniqueNumbers = new HashSet<>();
int n = word.length();
for (int i = 0; i < n; ) {
if (Character.isDigit(word.charAt(i))) {
int j = i;
while (j < n && Character.isDigit(word.charAt(j))) j++;
while (i < j && word.charAt(i) == '0') i++;
uniqueNumbers.add(word.substring(i, j));
i = j;
} else {
i++;
}
}
return uniqueNumbers.size();
}
public static void main(String[] args) {
System.out.println(numDifferentIntegers("a123bc34d8ef34"));
}
}#include <iostream>
#include <unordered_set>
using namespace std;
int numDifferentIntegers(string word) {
unordered_set<string> nums;
int n = word.size();
for (int i = 0; i < n; ) {
if (isdigit(word[i])) {
int j = i;
while (j < n && isdigit(word[j])) j++;
while (i < j && word[i] == '0') i++;
nums.insert(word.substr(i, j-i));
i = j;
} else {
i++;
}
}
return nums.size();
}
int main() {
cout << numDifferentIntegers("a123bc34d8ef34") << endl;
return 0;
}function numDifferentIntegers(word) {
const numSet = new Set();
let i = 0;
while (i < word.length) {
if (!isNaN(word[i]) && word[i] !== ' ') {
let j = i;
while (j < word.length && !isNaN(word[j]) && word[j] !== ' ') {
j++;
}
let num = BigInt(word.slice(i, j)).toString();
numSet.add(num);
i = j;
} else {
i++;
}
}
return numSet.size;
}
console.log(numDifferentIntegers("a123bc34d8ef34"));#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <ctype.h>
int numDifferentIntegers(char *word) {
int length = strlen(word);
char encounteredIntegers[1001][1001];
int setSize = 0;
for (int i = 0; i < length;) {
if (isdigit(word[i])) {
int start = i;
while (i < length && isdigit(word[i])) i++;
int end = i;
while (start < end && word[start] == '0') start++;
int exists = 0;
for (int j = 0; j < setSize; j++) {
if (strncmp(encounteredIntegers[j], &word[start], end - start) == 0) {
exists = 1;
break;
}
}
if (!exists) {
strncpy(encounteredIntegers[setSize], &word[start], end - start);
encounteredIntegers[setSize][end - start] = '\0';
setSize++;
}
} else {
i++;
}
}
return setSize;
}
int main() {
char word[] = "a123bc34d8ef34";
printf("%d\n", numDifferentIntegers(word));
return 0;
}using System;
using System.Collections.Generic;
public class Solution {
public int NumDifferentIntegers(string word) {
var numSet = new HashSet<string>();
int i = 0;
while (i < word.Length) {
if (char.IsDigit(word[i])) {
int j = i;
while (j < word.Length && char.IsDigit(word[j])) j++;
string num = word.Substring(i, j - i).TrimStart('0');
if (num == "") num = "0";
numSet.Add(num);
i = j;
} else {
i++;
}
}
return numSet.Count;
}
public static void Main() {
Solution sol = new Solution();
Console.WriteLine(sol.NumDifferentIntegers("a123bc34d8ef34"));
}
}Python's implementation of a sliding window tracks each digit block, prunes leading zeros, and fits substrings into a set. The track of i and j adheres to start and end markers in each stride.
Time Complexity: O(n), marked by per-character traversal and stripping operations.
Space Complexity: O(k), representing distinct integers stored in a set.
Approach 3: Double Pointers + Simulation
Traverse the string word, find the start and end positions of each integer, cut out this substring, and store it in the hash set s.
After the traversal, return the size of the hash set s.
Note, the integer represented by each substring may be very large, we cannot directly convert it to an integer. Therefore, we can remove the leading zeros of each substring before storing it in the hash set.
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the string word.
function numDifferentIntegers(word: string): number {
return new Set(
word
.replace(/\D+/g, ' ')
.trim()
.split(' ')
.filter(v => v !== '')
.map(v => v.replace(/^0+/g, '')),
).size;
}func numDifferentIntegers(word string) int {
s := map[string]struct{}{}
n := len(word)
for i := 0; i < n; i++ {
if word[i] >= '0' && word[i] <= '9' {
for i < n && word[i] == '0' {
i++
}
j := i
for j < n && word[j] >= '0' && word[j] <= '9' {
j++
}
s[word[i:j]] = struct{}{}
i = j
}
}
return len(s)
}use std::collections::HashSet;
impl Solution {
pub fn num_different_integers(word: String) -> i32 {
let s = word.as_bytes();
let n = s.len();
let mut set = HashSet::new();
let mut i = 0;
while i < n {
if s[i] >= b'0' && s[i] <= b'9' {
let mut j = i;
while j < n && s[j] >= b'0' && s[j] <= b'9' {
j += 1;
}
while i < j - 1 && s[i] == b'0' {
i += 1;
}
set.insert(String::from_utf8(s[i..j].to_vec()).unwrap());
i = j;
} else {
i += 1;
}
}
set.len() as i32
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| String Manipulation and Set Storage | Time Complexity: O(n), primarily decided by the length of the string and number of tokens. |
| Two-Pointer Sliding Window | Time Complexity: O(n), marked by per-character traversal and stripping operations. |
| Double Pointers + Simulation | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| String Manipulation and Set Storage | O(n) | O(n) | General case. Simple implementation when extracting numbers directly from the string. |
| Two-Pointer Sliding Window | O(n) | O(n) | Useful when treating digit sequences as windows or when extending to substring-based problems. |
Frequently asked questions
Is Number of Different Integers in a String easy or hard?
This problem is classified as Easy on LeetCode. The main challenge is correctly extracting numbers from the string and handling leading zeros so values like "001" and "1" are treated as the same integer.
How to solve Number of Different Integers in a String in O(n)?
Traverse the string and detect continuous digit segments. For each segment, remove leading zeros and store the normalized number in a hash set. Because the string is scanned once and each insertion is constant time on average, the algorithm achieves O(n) time complexity.
Number of Different Integers in a String Python or Java solution?
Both Python and Java implementations follow the same pattern: iterate through the string, collect digit substrings, strip leading zeros, and insert them into a set (HashSet in Java, set in Python). The final answer is the number of elements in the set with O(n) time complexity.
What is the best approach for Number of Different Integers in a String?
The most efficient approach scans the string once, extracts digit sequences, removes leading zeros, and stores each normalized number in a hash set. The set automatically removes duplicates, so the result is the set size. This method runs in O(n) time with O(n) space.
Is Number of Different Integers in a String asked at Google/Amazon/Meta?
String parsing and hash set problems similar to this frequently appear in interviews at companies like Amazon, Google, and Meta. Variations often test extracting tokens from strings, handling leading zeros, and counting unique elements efficiently.
What data structure is used in Number of Different Integers in a String?
A hash set is the primary data structure. It stores each parsed integer as a normalized string so duplicates are automatically removed. The problem also relies on string traversal and sometimes two-pointer techniques to identify digit substrings.
What is the time complexity of Number of Different Integers in a String?
The optimal solution runs in O(n) time where n is the length of the string. Each character is processed once while extracting numeric substrings. Hash set insertions and lookups are average O(1), leading to overall linear complexity with O(n) space.