algoadvance

Leetcode 1796. Second Largest Digit in a String

Problem Statement

You are given an alphanumeric string s. (Alphanumeric string is a string consisting of lowercase English letters and digits).

You have to find the second largest numerical digit that appears in s. If it does not exist, return -1.

Clarifying Questions

1. Input Constraints:
   • What is the length of the string s?
     • The string length can be up to 500 characters.
   • How should the result be returned if there are no numerical digits or only one unique numerical digit in the string?
     • In such cases, the result should be -1.

Strategy

1. Initialization:
   • Use a set to store unique digits encountered in the string.
2. Processing the String:
   • Traverse each character in the string.
   • If the character is a digit, add it to the set of digits.
3. Finding the Second Largest:
   • If the set has fewer than 2 unique digits, return -1.
   • Otherwise, sort the digits in descending order and return the second element in the sorted list.

Code

import java.util.TreeSet;

public class SecondLargestDigit {
    public int secondHighest(String s) {
        // Using TreeSet to automatically sort the digits in natural order
        TreeSet<Integer> digits = new TreeSet<>();
        
        // Traverse the string
        for (char c : s.toCharArray()) {
            if (Character.isDigit(c)) {
                // Add the digit to the set
                digits.add(Character.getNumericValue(c));
            }
        }
        
        // Check if we have at least two distinct digits
        if (digits.size() < 2) {
            return -1;
        }
        
        // Remove the largest element
        digits.pollLast();
        
        // The next largest element is now the highest element in the set
        return digits.last();
    }

    public static void main(String[] args) {
        SecondLargestDigit solution = new SecondLargestDigit();
        System.out.println(solution.secondHighest("dfa12321afd")); // Output: 2
        System.out.println(solution.secondHighest("abc1111")); // Output: -1
    }
}

Time Complexity

• Time Complexity:
  • Building the set and processing each character in the string takes O(n).
  • TreeSet operations like add and pollLast are O(log k), where k is the number of unique digits (0-9, so k ≤ 10).
  • Hence, in the worst case, it can be considered O(n) overall due to linear traversal of string length n.
• Space Complexity:
  • O(1), because the number of unique digits is at most 10.

This solution is efficient given the constraint of the string length up to 500 characters.

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

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?