algoadvance

Leetcode 423. Reconstruct Original Digits from English

Problem Statement

Given a non-empty string containing an out-of-order English representation of digits 0-9, reconstruct the digits in ascending order. For example, given “owoztneoer”, output should be “012”.

Clarifying Questions

  1. Input Constraints?
    • The input string will contain only lowercase English letters and have a length of at most 10^5.
  2. Character Distribution?
    • Each character in the input string belongs to the English representation of one of the digits 0-9.
  3. Output Format?
    • The output should be a string with digits 0-9 concatenated in ascending order.

Strategy

  1. Unique Identifier Characters:
    • Assocation of unique identifying characters with specific digits:
      • ‘z’ -> 0 : “zero”
      • ‘w’ -> 2 : “two”
      • ‘u’ -> 4 : “four”
      • ‘x’ -> 6 : “six”
      • ‘g’ -> 8 : “eight”
    • After counting these, we can move to partially unique identifiers for other digits:
      • ‘o’ -> 1 (after removing 0, 2, 4)
      • ‘h’ -> 3 (after removing 8)
      • ‘f’ -> 5 (after removing 4)
      • ’s’ -> 7 (after removing 6)
      • ‘i’ -> 9 (after removing 5, 6, 8)
  2. Frequency Counting:
    • We count the occurrence of each English character in the provided string.
    • We use the unique characters to determine the count of each digit.
    • After determining counts, construct the final digit string in ascending order.

Code

Here’s the Java code to solve the problem:

import java.util.HashMap;
import java.util.Map;

public class Solution {
    public String originalDigits(String s) {
        int[] count = new int[10]; // Array to store count of each digit
        int[] charCount = new int[26]; // Array to store count of each character

        // Count the frequency of each character in the input string
        for (char ch : s.toCharArray()) {
            charCount[ch - 'a']++;
        }

        // Identify counts using unique characters
        count[0] = charCount['z' - 'a'];
        count[2] = charCount['w' - 'a'];
        count[4] = charCount['u' - 'a'];
        count[6] = charCount['x' - 'a'];
        count[8] = charCount['g' - 'a'];

        // Identify counts using partially unique characters
        count[1] = charCount['o' - 'a'] - count[0] - count[2] - count[4];
        count[3] = charCount['h' - 'a'] - count[8];
        count[5] = charCount['f' - 'a'] - count[4];
        count[7] = charCount['s' - 'a'] - count[6];
        count[9] = charCount['i' - 'a'] - count[5] - count[6] - count[8];

        // Build the output string from digit counts
        StringBuilder result = new StringBuilder();
        for (int i = 0; i <= 9; i++) {
            for (int j = 0; j < count[i]; j++) {
                result.append(i);
            }
        }

        return result.toString();
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        String s = "owoztneoer";
        System.out.println(solution.originalDigits(s)); // Output: "012"
    }
}

Time Complexity

So, the overall time complexity is O(n) and the space complexity is O(1), not counting the input string itself since all auxiliary space usage is either constant or dependent on a fixed range (0-9 digits).

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