algoadvance

Leetcode 1805. Number of Different Integers in a String

Problem Statement

You are given a string word consisting of digits and lowercase English letters. You need to extract all the different integers that are present in the string and return the count of these distinct integers.

An integer is a contiguous sequence of digits within the string. Leading zeros are allowed in an integer but they should be ignored while determining if two integers are distinct.

Clarifying Questions

  1. Input Constraints: What is the length of the input string?
    • The length of the string word will be between 1 and 1000.
  2. Character Composition: Does the input string contain any special characters or uppercase letters?
    • No, the input string contains only digits and lowercase English letters.
  3. Result Requirements: What should be returned if there are no numbers in the string?
    • If no numbers are present in the string, the return value should be 0.
  4. Leading Zeros: How should leading zeros be handled?
    • Leading zeros should be ignored when determining distinct integers. For example, “001” and “1” should be considered the same integer.

Strategy

  1. Data Extraction: Iterate through the string and extract contiguous sequences of digits.
  2. Normalization: Convert these sequences to integers, which automatically handles the removal of leading zeros.
  3. Storage: Use a set to store these integers. A set inherently handles the uniqueness property.
  4. Count: The size of the set at the end of the process will give the count of distinct integers.

Code

import java.util.HashSet;
import java.util.Set;

public class Solution {
    public int numDifferentIntegers(String word) {
        Set<String> uniqueIntegers = new HashSet<>();
        int n = word.length();
        int i = 0;

        while (i < n) {
            // Skip non-digit characters
            while (i < n && !Character.isDigit(word.charAt(i))) {
                i++;
            }
            
            if (i < n && Character.isDigit(word.charAt(i))) {
                int j = i;
                // Find the end of the digit sequence
                while (j < n && Character.isDigit(word.charAt(j))) {
                    j++;
                }

                // Extract the number sequence
                String number = word.substring(i, j);

                // Remove leading zeros
                number = number.replaceFirst("^0+(?!$)", "");
                
                // Add the normalized number to the set
                uniqueIntegers.add(number);

                // Move to the next segment
                i = j;
            }
        }

        return uniqueIntegers.size();
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        String input = "a123bc34d8ef34";
        System.out.println(solution.numDifferentIntegers(input)); // Output: 3
    }
}

Time Complexity

Thus, the overall time complexity is O(n).

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI