Leetcode 1805: Number of Different Integers in a String

Input: The input consists of a single string `word` that contains both digits and lowercase letters.

Example: word = 'a456b789c456'

Constraints:

• 1 <= word.length <= 1000

• word consists of digits and lowercase English letters

Output: Return the number of distinct integers after performing the replacement operations on `word`.

Example: Output: 2

Constraints:

• The integers are compared based on their value, ignoring leading zeros.

Goal: To count how many distinct integers can be formed after replacing non-digit characters with spaces.

Steps:

• Replace every non-digit character in `word` with a space.

• Extract all sequences of digits from the string.

• Remove any leading zeros from each sequence and count distinct values.

Goal: The solution should handle strings with a length of up to 1000 characters and manage leading zeros appropriately.

Steps:

• Handle edge cases such as leading zeros in the digits and non-digit characters scattered throughout the string.

Assumptions:

• The string `word` will always contain at least one character.

• Input: word = 'a456b789c456'

• Explanation: After replacing non-digit characters, the string becomes ' 456 789 456'. There are two distinct integers: '456' and '789'.

Approach: The approach uses string manipulation to replace non-digit characters and count distinct integers by removing leading zeros.

Observations:

• We need to replace non-digit characters and ensure leading zeros do not affect the comparison of integers.

• Using a set to store the distinct integers (after removing leading zeros) ensures we only count unique integers.

Steps:

• Iterate through the string and replace non-digit characters with spaces.

• Split the resulting string on spaces to extract all digit sequences.

• Convert each sequence to an integer to eliminate leading zeros, then store it in a set.

• Return the size of the set, which contains the number of distinct integers.

Empty Inputs:

• There will always be at least one character in the input string.

Large Inputs:

• For large input strings, ensure that the solution is efficient, as the length of `word` can be up to 1000.

Special Values:

• Consider cases where the string contains many consecutive non-digit characters, or where all characters are digits.

Constraints:

• The solution should handle up to 1000 characters and large inputs efficiently.

int numDifferentIntegers(string w) {
    unordered_set<string> s{""};    
    for (int i = 0, j = 0; j <= w.size(); ++j) {
        if (j < w.size() && isdigit(w[j]))
            i += i < j && w[i] == '0';
        else {
            s.insert(w.substr(i, j - i));
            i = j + 1;
        }
    }
    return s.size() - 1;
}

1 : Function Definition

int numDifferentIntegers(string w) {

Define the function `numDifferentIntegers` which takes a string `w` as input and returns an integer representing the number of distinct integer values.

2 : Variable Initialization

    unordered_set<string> s{""};

Initialize an unordered set `s` to store unique integer substrings found in the input string `w`.

3 : Loop and Recursion

    for (int i = 0, j = 0; j <= w.size(); ++j) {

Start a loop with two variables `i` and `j`, where `i` tracks the start of a number, and `j` iterates over each character in the string `w`.

4 : Conditionals

        if (j < w.size() && isdigit(w[j]))

Check if the character at position `j` is a digit and if `j` is within the bounds of the string.

5 : Mathematical Operations

            i += i < j && w[i] == '0';

If a leading zero is encountered at position `i`, adjust `i` to skip over it and start from the next digit.

6 : Flow Control

        else {

If the current character is not a digit, proceed with the following actions.

7 : Set Insertion

            s.insert(w.substr(i, j - i));

Insert the substring of `w` from index `i` to `j` into the set `s`, which ensures only unique numbers are stored.

8 : Variable Initialization

            i = j + 1;

Update `i` to the next index after `j` to start searching for the next potential number.

9 : Return

    return s.size() - 1;

Return the size of the set `s` (number of unique integer substrings) minus one to exclude the empty string.

Best Case: O(n)

Average Case: O(n)

Worst Case: O(n)

Description: The time complexity is O(n) where n is the length of the input string, as we perform a single pass over the string and extract distinct integers.

Best Case: O(n)

Worst Case: O(n)

Description: The space complexity is O(n) to store the integers in the set.

Leetcode 1805: Number of Different Integers in a String

Explore →