Reconstruct Original Digits From English

                                            
class Solution {
public:
    string originalDigits(string s) {
        vector<int> count(10, 0);
        vector<int> letters(26, 0);
        for (char c : s) {
            letters[c - 'a']++;
        }
        count[0] = letters['z' - 'a'];
        count[2] = letters['w' - 'a'];
        count[4] = letters['u' - 'a'];
        count[6] = letters['x' - 'a'];
        count[8] = letters['g' - 'a'];
        count[3] = letters['h' - 'a'] - count[8];
        count[5] = letters['f' - 'a'] - count[4];
        count[7] = letters['s' - 'a'] - count[6];
        count[9] = letters['i' - 'a'] - count[5] - count[6] - count[8];
        count[1] = letters['o' - 'a'] - count[0] - count[2] - count[4];
        
        string res = "";
        for (int i = 0; i < 10; i++) {
            res += string(count[i], '0' + i);
        }
        return res;
    }
};

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

                                            
class Solution(object):
    def originalDigits(self, s):
        """
        :type s: str
        :rtype: str
        """
        count = collections.Counter(s)
        
        num = [0]*10
        num[0] = count['z']
        num[2] = count['w']
        num[4] = count['u']
        num[6] = count['x']
        num[8] = count['g']
        num[3] = count['h'] - num[8]
        num[5] = count['f'] - num[4]
        num[7] = count['s'] - num[6]
        num[9] = count['i'] - num[5] - num[6] - num[8]
        num[1] = count['n'] - 2*num[9] - num[7]
        
        res = ""
        for i in range(10):
            res += str(i)*num[i]
        
        return res

                                            
char* originalDigits(char* s) {
    int count[10] = {0};
    int letter_count[26] = {0};
    int i, len = strlen(s);
    char *result = (char*)malloc(sizeof(char) * (len + 1));
    char str[2];
    
    for(i = 0; i < len; i++) {
        letter_count[s[i] - 'a']++;
    }
    
    count[0] = letter_count['z' - 'a'];
    count[2] = letter_count['w' - 'a'];
    count[4] = letter_count['u' - 'a'];
    count[6] = letter_count['x' - 'a'];
    count[8] = letter_count['g' - 'a'];
    count[1] = letter_count['o' - 'a'] - count[0] - count[2] - count[4];
    count[3] = letter_count['h' - 'a'] - count[8];
    count[5] = letter_count['f' - 'a'] - count[4];
    count[7] = letter_count['s' - 'a'] - count[6];
    count[9] = letter_count['i' - 'a'] - count[5] - count[6] - count[8];
    
    result[0] = '\0';
    
    for(i = 0; i < 10; i++) {
        while(count[i] > 0) {
            str[0] = i + '0';
            str[1] = '\0';
            strcat(result, str);
            count[i]--;
        }
    }
    
    return result;
}

                                            
public class Solution {
    public string OriginalDigits(string s) {
        int[] count = new int[10];
        foreach (char ch in s) {
            if (ch == 'z') count[0]++;
            if (ch == 'w') count[2]++;
            if (ch == 'u') count[4]++;
            if (ch == 'x') count[6]++;
            if (ch == 'g') count[8]++;
            if (ch == 'o') count[1]++;
            if (ch == 't') count[3]++;
            if (ch == 'f') count[5]++;
            if (ch == 's') count[7]++;
            if (ch == 'i') count[9]++;
        }
        
        count[1] -= count[0] + count[2] + count[4];
        count[3] -= count[2] + count[8];
        count[5] -= count[4];
        count[7] -= count[6];
        count[9] -= count[5] + count[6] + count[8];
        
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < 10; i++) {
            while (count[i] > 0) {
                sb.Append(i);
                count[i]--;
            }
        }
        
        return sb.ToString();
    }
}

                                            
/**
 * @param {string} s
 * @return {string}
 */
var originalDigits = function(s) {
    let count = new Array(10).fill(0);
    
    for (let i = 0; i < s.length; i++) {
        if (s[i] === 'z') count[0]++;
        if (s[i] === 'w') count[2]++;
        if (s[i] === 'u') count[4]++;
        if (s[i] === 'x') count[6]++;
        if (s[i] === 'g') count[8]++;
        if (s[i] === 's') count[7]++; // 7 and 6
        if (s[i] === 'f') count[5]++; // 5 and 4
        if (s[i] === 'h') count[3]++; // 3 and 8
        if (s[i] === 'i') count[9]++; // 9, 8, 6, and 5
        if (s[i] === 'o') count[1]++; // 1, 2, and 0
    }
    
    count[7] -= count[6];
    count[5] -= count[4];
    count[3] -= count[8];
    count[9] -= count[8] + count[6] + count[5];
    count[1] -= count[0] + count[2] + count[4];
    
    let result = '';
    for (let i = 0; i < 10; i++) {
        result += String(i).repeat(count[i]);
    }
    
    return result;
};

                                            
function originalDigits(s: string): string {
    const count: { [key: string]: number } = {};
    const uniqueChars: string[] = ['z', 'w', 'u', 'x', 'g', 'o', 'r', 'f', 'v', 'i'];
    const nums: number[] = [0, 2, 4, 6, 8, 1, 3, 5, 7, 9];
    const words: string[] = ['zero', 'one', 'two', 'three', 'four', 'five', 'six', 'seven', 'eight', 'nine'];

    for (const char of s) {
        count[char] = (count[char] || 0) + 1;
    }

    const res: number[] = [];

    for (let i = 0; i < uniqueChars.length; i++) {
        const char = uniqueChars[i];
        const num = nums[i];
        const word = words[num];

        if (count[char] && count[char] > 0) {
            const occurrences = count[char];
            for (const c of word) {
                count[c] -= occurrences;
            }
            res.push(num);
        }
    }

    return res.sort((a, b) => a - b).join('');
};

                                            
class Solution {
    /**
     * @param String $s
     * @return String
     */
    function originalDigits($s) {
        $count = array_fill(0, 10, 0);
        $charCount = [];
        $output = '';
        
        for ($i = 0; $i < strlen($s); $i++) {
            $charCount[$s[$i]] = isset($charCount[$s[$i]]) ? $charCount[$s[$i]] + 1 : 1;
        }
        
        $count[0] = $charCount['z'] ?? 0;
        $count[2] = $charCount['w'] ?? 0;
        $count[4] = $charCount['u'] ?? 0;
        $count[6] = $charCount['x'] ?? 0;
        $count[8] = $charCount['g'] ?? 0;
        
        $count[1] = ($charCount['o'] ?? 0) - $count[0] - $count[2] - $count[4];
        $count[3] = ($charCount['h'] ?? 0) - $count[8];
        $count[5] = ($charCount['f'] ?? 0) - $count[4];
        $count[7] = ($charCount['s'] ?? 0) - $count[6];
        $count[9] = ($charCount['i'] ?? 0) - $count[5] - $count[6] - $count[8];
        
        for ($i = 0; $i <= 9; $i++) {
            $output .= str_repeat($i, $count[$i]);
        }
        
        return $output;
    }
}

                                            
class Solution {
    func originalDigits(_ s: String) -> String {
        var count: [Character: Int] = [:]
        var res: [Int] = Array(repeating: 0, count: 10)
        
        for char in s {
            count[char, default: 0] += 1
        }
        
        res[0] = count["z", default: 0]
        res[2] = count["w", default: 0]
        res[4] = count["u", default: 0]
        res[6] = count["x", default: 0]
        res[8] = count["g", default: 0]
        res[3] = count["h", default: 0] - res[8]
        res[5] = count["f", default: 0] - res[4]
        res[7] = count["v", default: 0] - res[5]
        res[9] = count["i", default: 0] - res[5] - res[6] - res[8]
        res[1] = count["o", default: 0] - res[0] - res[2] - res[4]
        
        var result: [String] = []
        for (i, value) in res.enumerated() {
            if value > 0 {
                result.append(String(repeating: "\(i)", count: value))
            }
        }
        
        return result.joined()
    }
}

                                            
class Solution {
    fun originalDigits(s: String): String {
        val count = IntArray(10)
        val ch = intArrayOf('z'.toInt(), 'w'.toInt(), 'u'.toInt(), 'x'.toInt(), 'g'.toInt(), 'f'.toInt(), 's'.toInt(), 'i'.toInt(), 'o'.toInt(), 't'.toInt())
        val nums = intArrayOf(0, 2, 4, 6, 8, 5, 7, 9, 1, 3)
        val chars = arrayOf("zero", "two", "four", "six", "eight", "five", "seven", "nine", "one", "three")
        
        val lettersCount = IntArray(26)
        for (letter in s) {
            lettersCount[letter - 'a']++
        }
        
        for (i in nums.indices) {
            val num = nums[i]
            val letter = chars[i]
            val index = ch[i] - 'a'.toInt()
            val countLetter = lettersCount[index]
            
            if (countLetter > 0) {
                count[num] = countLetter
                for (l in letter) {
                    lettersCount[l.toInt() - 'a'.toInt()] -= countLetter
                }
            }
        }
        
        val res = StringBuilder()
        for (i in 0 until 10) {
            for (j in 0 until count[i]) {
                res.append(i)
            }
        }
        
        return res.toString()
    }
}

                                            
func originalDigits(s string) string {
    count := make(map[byte]int)
    digits := make([]int, 10)

    for i := 0; i < len(s); i++ {
        count[s[i]]++
    }

    digits[0] = count['z']
    digits[2] = count['w']
    digits[4] = count['u']
    digits[6] = count['x']
    digits[8] = count['g']
    digits[3] = count['h'] - digits[8]
    digits[5] = count['f'] - digits[4]
    digits[7] = count['s'] - digits[6]
    digits[9] = count['i'] - digits[5] - digits[6] - digits[8]
    digits[1] = count['n'] - 2*digits[9] - digits[7]

    result := ""
    for i := 0; i < 10; i++ {
        for j := 0; j < digits[i]; j++ {
            result += string('0' + i)
        }
    }

    return result
}

                                            
# @param {String} s
# @return {String}
def original_digits(s)
    counts = Hash.new(0)
    result = ""
    
    s.chars.each do |char|
        counts[char] += 1
    end
    
    counts["0"] = counts["z"]
    counts["2"] = counts["w"]
    counts["4"] = counts["u"]
    counts["6"] = counts["x"]
    counts["8"] = counts["g"]
    counts["3"] = counts["h"] - counts["8"]
    counts["5"] = counts["f"] - counts["4"]
    counts["7"] = counts["s"] - counts["6"]
    counts["9"] = counts["i"] - counts["5"] - counts["6"] - counts["8"]
    counts["1"] = counts["n"] - counts["7"] - 2 * counts["9"]
    
    "0123456789".each_char do |char|
        result += char * counts[char].to_i
    end
    
    return result
end

                                            
object Solution {
    def originalDigits(s: String): String = {
        val digits = Array.ofDim[Int](10)
        val charCount = Array.ofDim[Int](26)
        
        for (c <- s) {
            charCount(c - 'a') += 1
        }
        
        digits(0) = charCount('z' - 'a')
        digits(2) = charCount('w' - 'a')
        digits(4) = charCount('u' - 'a')
        digits(6) = charCount('x' - 'a')
        digits(8) = charCount('g' - 'a')
        
        digits(3) = charCount('h' - 'a') - digits(8)
        digits(5) = charCount('f' - 'a') - digits(4)
        digits(7) = charCount('s' - 'a') - digits(6)
        
        digits(1) = charCount('o' - 'a') - digits(0) - digits(2) - digits(4)
        digits(9) = charCount('i' - 'a') - digits(5) - digits(6) - digits(8)
        
        val sb = new StringBuilder()
        for (i <- 0 to 9; j <- 0 until digits(i)) {
            sb.append(i)
        }
        
        sb.toString()
    }
}

To solve this coding challenge, we need to extract and reconstruct the original digits (0-9) from a scrambled string of English words that represent these digits. The goal is to return these digits in ascending order.

Explanation

Let's break down the problem and its solution step-by-step. The provided string contains jumbled representations of English words for digits 0 through 9. Each digit has a unique letter or a combination of letters that can help us identify its presence in the scrambled string. For example:

The word "zero" contains the unique letter 'z'.
The word "two" contains the unique letter 'w'.
The word "four" contains the unique letter 'u'.
And so forth...

The strategy involves counting occurrences of these unique characters to determine the frequency of each digit, then updating the counts by accounting for overlapping characters across various digits.

Step-by-Step Explanation:

Count Frequency of Letters : Use a hash map to count the frequency of each character in the scrambled string.
Identify Unique Digits : Use the unique characters that appear in only one digit's word to determine the initial counts of those unique digits.
Adjust for Overlapping Characters : Once the unique digits are counted, adjust counts for the remaining digits that share characters by subtracting the counts of already identified digits.
Reconstruct Digit String : Finally, construct the resulting number string from the digit counts in ascending order.

Detailed Steps in Pseudocode:

Count Frequency of Letters :

                                            
# Create an empty hash map to store character counts
char_count = {}

# Iterate over each character in the string s and update the hash map
for each character in s:
if character in char_count:
char_count[character] += 1
else:
char_count[character] = 1

Identify Unique Digits Based on Unique Letters :

                                            
# Create an array to store counts of each digit from 0 to 9
digit_counts = array of size 10 initialized to 0

# Identify counts for digits with unique determining letters
digit_counts[0] = char_count['z']  # "zero" has unique 'z'
digit_counts[2] = char_count['w']  # "two" has unique 'w'
digit_counts[4] = char_count['u']  # "four" has unique 'u'
digit_counts[6] = char_count['x']  # "six" has unique 'x'
digit_counts[8] = char_count['g']  # "eight" has unique 'g'

Adjust for Overlapping Characters :

                                            
# Adjust counts for other digits by subtracting already known counts
digit_counts[3] = char_count['h'] - digit_counts[8]  # "three" has shared 'h' with "eight"
digit_counts[5] = char_count['f'] - digit_counts[4]  # "five" has shared 'f' with "four"
digit_counts[7] = char_count['s'] - digit_counts[6]  # "seven" has shared 's' with "six"
digit_counts[9] = char_count['i'] - digit_counts[5] - digit_counts[6] - digit_counts[8]  # "nine" has shared 'i' with "five", "six", and "eight"
digit_counts[1] = char_count['n'] - (2 * digit_counts[9]) - digit_counts[7]  # "one" has shared 'n' with "nine" and "seven"

Reconstruct and Return the Result :

                                            
# Initialize an empty string for result
result = ""

# Construct the resulting digits string by iterating from 0 to 9
for i from 0 to 9:
    append digit i, digit_counts[i] times to result

# Return the reconstructed string containing digits in ascending order
return result

By carefully following these steps and leveraging the uniqueness of certain letters in the words representing digits, we can reconstruct the original sequence of digits from the given scrambled string efficiently and accurately.