Number Of Different Integers In A String - Leetcode Solution

Problem Statement:

Given a string s containing only digits, return the number of different integers that can be formed by deleting some (possibly zero) characters from s and not changing the relative order of the remaining characters.

Example: Input: s = "a123bc34d8ef34" Output: 3 Explanation: The three different integers are "123", "34", and "834".

Solution:

To solve this problem, we need to iterate through the string s and count the number of different integers that can be formed by deleting some characters and maintaining their relative order. We can do this by maintaining a set of all the different integers we have encountered so far.

Algorithm:

1. Create an empty set called integer_set to store all the different integers we encounter while iterating through the string.

2. Initialize a variable called current_number to an empty string.

3. Iterate through the string s character by character.

4. If the current character c is a digit, append it to the string current_number.

5. If the current character c is not a digit, then check if the string current_number is not empty. If it is not empty, then add the current_number to the set integer_set and reset the string current_number to an empty string.

6. After iterating through the entire string, check if the string current_number is not empty. If it is not empty, then add the current_number to the set integer_set.

7. Return the size of the set integer_set.

Python code:

class Solution: def numDifferentIntegers(self, s: str) -> int:

    # Step 1
    integer_set = set()
    
    # Step 2
    current_number = ""
    
    # Step 3
    for c in s:
        
        # Step 4
        if c.isdigit():
            current_number += c
            
        # Step 5
        else:
            if current_number:
                integer_set.add(int(current_number))
                current_number = ""
                
    # Step 6
    if current_number:
        integer_set.add(int(current_number))
                
    # Step 7
    return len(integer_set)

1