Shuffle String — UnStop sample question

 Problem Statement

Mr. Agoji is given a shuffled string made by randomly shuffling a special string. A sting will be called special only if it is formed by joining some special words any number of times. Special words are mapping of numbers (0 <= number < 10) to their words, for example, mapping of ‘0’ to ‘zero’, mapping of ‘1’ to ‘one’, and so on. Mr. Agoji is asked to convert the shuffled string to the smallest special number. A special number is a number formed using numbers (0 <= number < 10) without any leading zeroes. Mr. Agoji being not so good with numbers and strings ask for your help.

Input Format

The first line of the input will contain T, the number of test cases, 1 <= T <= 100 For each test case, There will be a, s shuffled string, on a separate line

1 <= s.length <= 100000

Output Format

For each test case, on the new line, the Smallest special number is in the string format. Some notes on output: Shuffled string will always be able to convert into at least one valid special string. Shuffled string will only contain small English alphabets. If a shuffled string contains only zeroes, you should output “0”.

Approach:

1. create a map of digit to words
2. create frequency map of characters from input string
3. Traverse all digits from 0 to 9 and see how many numbers are represented in string. save it in digit_freq dictionary
4. sort all numbers in digit_freq and create a string from that
5. There are few edge case we need to take care. If all are zero then return 0. Another edge case is we cant keep 0 in front positions of the result string. we can keep all zeros after first non zero digit to create smallest number according to requirement.

Python Code:

def smallest_special_number(string):
    num_to_word = {
        '0' : 'zero', 
        '1' : 'one', 
        '2' : 'two',  
        '3' : 'three', 
        '4' : 'four', 
        '5' : 'five', 
        '6' : 'six', 
        '7' : 'seven', 
        '8' : 'eight', 
        '9' : 'nine',
    }

    char_freq = {}
    for char in string:
        if char not in char_freq:
            char_freq[char] = 1
        else:
            char_freq[char] += 1
    
    digit_freq = {}
    for digit in num_to_word:
        word = num_to_word[digit]
        count = char_freq.get(word[0], 0)
        for char in word[1:]:
            count = min(count, char_freq.get(char, 0))
        digit_freq[digit] = count
    result = ''
    for num in sorted(digit_freq.keys()):
        result += num * digit_freq[num]
    
    # Handle special cases
    if len(result) == 0:
        return '0'
    if result[0] == '0':
        zeros = 1
        for i in range(1, len(result)):
            if result[i] == '0':
                zeros += 1
            else:
                break
    if zeros == len(result):
        return '0'
    if zeros != 0:
        result = result[i] + '0' * zeros + result[i+1:]
    return result



# Read input and process test cases
s = "ewtooetzrowon"
print(smallest_special_number(s))

Java Code:

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int t = scanner.nextInt();
        scanner.nextLine();
        while (t-- > 0) {
            String s = scanner.nextLine();
            String result = smallestSpecialNumber(s);
            System.out.println(result);
        }
        scanner.close();
    }

    public static String smallestSpecialNumber(String string) {
        Map<Character, String> numToWord = new HashMap<Character, String>() {{
            put('0', "zero");
            put('1', "one");
            put('2', "two");
            put('3', "three");
            put('4', "four");
            put('5', "five");
            put('6', "six");
            put('7', "seven");
            put('8', "eight");
            put('9', "nine");
        }};

        Map<Character, Integer> charFreq = new HashMap<>();
        for (char c : string.toCharArray()) {
            charFreq.put(c, charFreq.getOrDefault(c, 0) + 1);
        }

        Map<Character, Integer> digitFreq = new HashMap<>();
        for (char digit : numToWord.keySet()) {
            String word = numToWord.get(digit);
            int count = charFreq.getOrDefault(word.charAt(0), 0);
            for (int i = 1; i < word.length(); i++) {
                count = Math.min(count, charFreq.getOrDefault(word.charAt(i), 0));
            }
            digitFreq.put(digit, count);
        }

        StringBuilder sb = new StringBuilder();
        for (char digit = '0'; digit <= '9'; digit++) {
            int freq = digitFreq.getOrDefault(digit, 0);
            sb.append(String.valueOf(digit).repeat(freq));
        }
        String result = sb.toString();

        // Handle special cases
        if (result.length() == 0) {
            return "0";
        }
        if (result.charAt(0) == '0') {
            int zeros = 1;
            int i = 1;
            for (; i < result.length(); i++) {
                if (result.charAt(i) == '0') {
                    zeros++;
                } else {
                    break;
                }
            }
            if (zeros == result.length()) {
                return "0";
            }
            result = result.charAt(i) + "0".repeat(zeros) + result.substring(i + 1);
        }
        return result;
    }
}

This is sample question given for Codegoda 2023 code Challenge. I didn’t get chance to test all testcases. Let me know if you can’t submit this code by any chance.