Mutating counts without cleanup
Wrong move: Zero-count keys stay in map and break distinct/count constraints.
Usually fails on: Window/map size checks are consistently off by one.
Fix: Delete keys when count reaches zero.
Move from brute-force thinking to an efficient approach using hash map strategy.
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 <= 105s[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.Problem summary: Given a string s containing an out-of-order English representation of digits 0-9, return the digits in ascending order.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Hash Map · Math
"owoztneoer"
"fviefuro"
Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #423: Reconstruct Original Digits from English
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();
}
}
// Accepted solution for LeetCode #423: Reconstruct Original Digits from English
func originalDigits(s string) string {
counter := make([]int, 26)
for _, c := range s {
counter[c-'a']++
}
cnt := make([]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]
ans := []byte{}
for i, c := range cnt {
ans = append(ans, bytes.Repeat([]byte{byte('0' + i)}, c)...)
}
return string(ans)
}
# Accepted solution for LeetCode #423: Reconstruct Original Digits from English
class Solution:
def originalDigits(self, s: str) -> str:
counter = Counter(s)
cnt = [0] * 10
cnt[0] = counter['z']
cnt[2] = counter['w']
cnt[4] = counter['u']
cnt[6] = counter['x']
cnt[8] = counter['g']
cnt[3] = counter['h'] - cnt[8]
cnt[5] = counter['f'] - cnt[4]
cnt[7] = counter['s'] - cnt[6]
cnt[1] = counter['o'] - cnt[0] - cnt[2] - cnt[4]
cnt[9] = counter['i'] - cnt[5] - cnt[6] - cnt[8]
return ''.join(cnt[i] * str(i) for i in range(10))
// Accepted solution for LeetCode #423: Reconstruct Original Digits from English
struct Solution;
use std::collections::HashMap;
impl Solution {
fn original_digits(s: String) -> String {
let digits = vec![
"zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine",
];
let digits: Vec<HashMap<char, usize>> = digits
.into_iter()
.map(|s| {
let mut hm: HashMap<char, usize> = HashMap::new();
for c in s.chars() {
*hm.entry(c).or_default() += 1;
}
hm
})
.collect();
let mut count: HashMap<char, usize> = HashMap::new();
for c in s.chars() {
*count.entry(c).or_default() += 1;
}
let mut res: Vec<char> = vec![];
for i in vec![0, 4, 5, 6, 7, 8, 3, 2, 1, 9].into_iter() {
let mut min = std::usize::MAX;
for (&c, &v) in &digits[i] {
if *count.entry(c).or_default() % v != 0 {
continue;
}
if *count.entry(c).or_default() / v < min {
min = *count.entry(c).or_default() / v;
}
}
if min != std::usize::MAX {
for (&c, &v) in &digits[i] {
*count.entry(c).or_default() -= min * v;
}
for _ in 0..min {
res.push((b'0' + i as u8) as char);
}
}
}
res.sort_unstable();
res.into_iter().collect()
}
}
#[test]
fn test() {
let s = "owoztneoer".to_string();
let res = "012".to_string();
assert_eq!(Solution::original_digits(s), res);
let s = "fviefuro".to_string();
let res = "45".to_string();
assert_eq!(Solution::original_digits(s), res);
}
// Accepted solution for LeetCode #423: Reconstruct Original Digits from English
// Auto-generated TypeScript example from java.
function exampleSolution(): void {
}
// Reference (java):
// // Accepted solution for LeetCode #423: Reconstruct Original Digits from English
// 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();
// }
// }
Use this to step through a reusable interview workflow for this problem.
For each element, scan the rest of the array looking for a match. Two nested loops give n × (n−1)/2 comparisons = O(n²). No extra space since we only use loop indices.
One pass through the input, performing O(1) hash map lookups and insertions at each step. The hash map may store up to n entries in the worst case. This is the classic space-for-time tradeoff: O(n) extra memory eliminates an inner loop.
Review these before coding to avoid predictable interview regressions.
Wrong move: Zero-count keys stay in map and break distinct/count constraints.
Usually fails on: Window/map size checks are consistently off by one.
Fix: Delete keys when count reaches zero.
Wrong move: Temporary multiplications exceed integer bounds.
Usually fails on: Large inputs wrap around unexpectedly.
Fix: Use wider types, modular arithmetic, or rearranged operations.