Scale Engineer

Reconstruct Original Digits from English

Med
#0410Time: O(K^10 * L) where K is the maximum possible count for any single digit, and L is the alphabet size (26). The recursion depth is 10, and at each level, we can branch up to K times. This is exponential and too slow for the given constraints.Space: O(1). The recursion depth is constant (10), and at each level, we store a character count array of constant size (26).3 companies
Patterns
Math
Data structures
Hash TableString
Companies
WixSalesforceNetApp

Prompt

Given a string s containing an out-of-order English representation of digits 0-9, return the digits in ascending order.

 

Example 1:

Input: s = "owoztneoer"
Output: "012"

Example 2:

Input: s = "fviefuro"
Output: "45"

 

Constraints:

  • 1 <= s.length <= 105
  • s[i] is one of the characters ["e","g","f","i","h","o","n","s","r","u","t","w","v","x","z"].
  • s is guaranteed to be valid.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach frames the problem as finding the correct count for each digit (0-9) that accounts for all characters in the input string. It uses a recursive backtracking algorithm to explore all possible combinations of digit counts.

Algorithm

  • Create a frequency map charCounts for the characters in s.
  • Create an array digitCounts of size 10 to store the result.
  • Define a recursive function backtrack(digit, currentCounts):
    • Base Case: If digit == 10, check if all values in currentCounts are 0. If yes, a solution is found, return true; otherwise, return false.
    • Determine the word for the current digit.
    • Calculate the maximum possible number of times (maxCount) this word can be formed from currentCounts.
    • Loop i from 0 to maxCount:
      • Set digitCounts[digit] = i.
      • Create nextCounts by subtracting characters for i copies of the word from currentCounts.
      • If backtrack(digit + 1, nextCounts) returns true, then a solution is found down this path, so return true.
    • If the loop completes, no solution was found for this branch. Return false.
  • Initiate the process with backtrack(0, charCounts).
  • If it returns true, build the result string from digitCounts by appending each digit the required number of times in ascending order.

Walkthrough

First, we count the frequency of each character in the input string s. We then define a recursive function, say backtrack(digit, counts), which tries to determine the number of occurrences for the current digit. The function iterates through all possible counts for the current digit, from 0 up to the maximum possible (limited by the available characters in counts). For each possible count, it subtracts the corresponding characters from the counts map and makes a recursive call for the next digit (digit + 1). If a recursive call returns true (meaning a valid combination was found for the subsequent digits), it means we've found a solution. We store the count for the current digit and also return true. The base case for the recursion is when we have considered all digits (i.e., digit == 10). At this point, if all character counts are zero, we have successfully reconstructed the original digits. Once the backtracking process successfully finds the counts for all digits, we construct the final string.

class Solution {    // Word representations for digits 0-9    String[] words = {"zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine"};    // Character counts for each word    int[][] wordCharCounts = new int[10][26];    // Resulting digit counts    int[] digitCounts = new int[10];     public String originalDigits(String s) {        // Pre-calculate character counts for each digit word        for (int i = 0; i < 10; i++) {            for (char c : words[i].toCharArray()) {                wordCharCounts[i][c - 'a']++;            }        }         // Count characters in the input string        int[] sCounts = new int[26];        for (char c : s.toCharArray()) {            sCounts[c - 'a']++;        }         // Start backtracking from digit 0        if (backtrack(0, sCounts)) {            StringBuilder result = new StringBuilder();            for (int i = 0; i < 10; i++) {                for (int j = 0; j < digitCounts[i]; j++) {                    result.append(i);                }            }            return result.toString();        }        return ""; // Should not happen based on problem constraints    }     private boolean backtrack(int digit, int[] currentCounts) {        if (digit == 10) {            // Base case: check if all characters have been used            for (int count : currentCounts) {                if (count != 0) {                    return false;                }            }            return true;        }         // Determine max possible count for the current digit's word        int maxCount = Integer.MAX_VALUE;        for (int i = 0; i < 26; i++) {            if (wordCharCounts[digit][i] > 0) {                maxCount = Math.min(maxCount, currentCounts[i] / wordCharCounts[digit][i]);            }        }         // Iterate through all possible counts for the current digit        for (int i = 0; i <= maxCount; i++) {            int[] nextCounts = new int[26];            System.arraycopy(currentCounts, 0, nextCounts, 0, 26);            for (int j = 0; j < 26; j++) {                nextCounts[j] -= i * wordCharCounts[digit][j];            }                        digitCounts[digit] = i;            if (backtrack(digit + 1, nextCounts)) {                return true;            }        }                return false;    }}

Complexity

Time

O(K^10 * L) where K is the maximum possible count for any single digit, and L is the alphabet size (26). The recursion depth is 10, and at each level, we can branch up to K times. This is exponential and too slow for the given constraints.

Space

O(1). The recursion depth is constant (10), and at each level, we store a character count array of constant size (26).

Trade-offs

Pros

  • It's a general approach that could work for similar problems where a direct counting trick isn't obvious.

Cons

  • Extremely inefficient due to its exponential time complexity.

  • Will result in a 'Time Limit Exceeded' (TLE) error for the given constraints.

  • More complex to implement correctly compared to the optimal solution.

Solutions

class Solution { public String originalDigits ( String s ) { int [] counter = new int [ 26 ]; for ( char c : s . toCharArray ()) { ++ counter [ c - 'a' ]; } int [] cnt = new int [ 10 ]; cnt [ 0 ] = counter [ 'z' - 'a' ]; cnt [ 2 ] = counter [ 'w' - 'a' ]; cnt [ 4 ] = counter [ 'u' - 'a' ]; cnt [ 6 ] = counter [ 'x' - 'a' ]; cnt [ 8 ] = counter [ 'g' - 'a' ]; cnt [ 3 ] = counter [ 'h' - 'a' ] - cnt [ 8 ]; cnt [ 5 ] = counter [ 'f' - 'a' ] - cnt [ 4 ]; cnt [ 7 ] = counter [ 's' - 'a' ] - cnt [ 6 ]; cnt [ 1 ] = counter [ 'o' - 'a' ] - cnt [ 0 ] - cnt [ 2 ] - cnt [ 4 ]; cnt [ 9 ] = counter [ 'i' - 'a' ] - cnt [ 5 ] - cnt [ 6 ] - cnt [ 8 ]; StringBuilder sb = new StringBuilder (); for ( int i = 0 ; i < 10 ; ++ i ) { for ( int j = 0 ; j < cnt [ i ]; ++ j ) { sb . append ( i ); } } return sb . toString (); } }

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem