algoadvance

Leetcode 2264. Largest 3

Problem Statement

You’re given a string num representing a large integer. Your task is to return the largest three-digit number that appears in the string num and is made up of the same digit. If no such number exists, return an empty string.

Clarifying Questions

  1. Input Format: What is the type of the input?
    • The input will be a single string.
  2. Size Constraints: Are there any constraints on the length of the string?
    • The length of the string can go up to 1000 characters.
  3. Character Set: Can the string contain characters other than digits?
    • The problem assumes that the string only contains numeric characters (0-9).

Strategy

  1. Iterate Through the String: Traverse the string while checking every substring of length 3.
  2. Check for Conditions: For each substring of length 3, check if all characters are the same.
  3. Keep Track of the Largest: Use a string or integer variable to keep track of the largest valid substring found.
  4. Return Result: After the loop, return the largest valid substring or an empty string if no valid substring was found.

Code

public class LargestThreeSameDigitNumber {
    public static String largestGoodInteger(String num) {
        String maxNumber = "";
        
        for (int i = 0; i < num.length() - 2; i++) {
            // Get each substring of length 3
            String sub = num.substring(i, i + 3);
            
            // Check if all three characters are the same
            if (sub.charAt(0) == sub.charAt(1) && sub.charAt(1) == sub.charAt(2)) {
                // Update the maxNumber if the current sub is greater
                if (sub.compareTo(maxNumber) > 0) {
                    maxNumber = sub;
                }
            }
        }
        
        return maxNumber;
    }

    public static void main(String[] args) {
        // Test cases
        System.out.println(largestGoodInteger("6777133339")); // Should print "777"
        System.out.println(largestGoodInteger("2300019"));    // Should print "000"
        System.out.println(largestGoodInteger("42352338"));   // Should print ""
        System.out.println(largestGoodInteger(""));           // Should print ""
    }
}

Time Complexity

This solution effectively traverses the input string once and compares fixed-length substrings, ensuring it runs efficiently even for the maximum input size.

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