Shuffle String — образец вопроса UnStop

Постановка задачи

Мистеру Агоджи дается перетасованная строка, полученная путем случайного перетасовки специальной строки. Стинг будет называться специальным только в том случае, если он образован соединением некоторых специальных слов любое количество раз. Специальные слова представляют собой отображение чисел (0 <= число < 10) в их слова, например, отображение «0» в «ноль», отображение «1» в «единицу» и т. д. Мистера Агоджи просят преобразовать перетасованную строку в наименьшее специальное число. Специальное число — это число, состоящее из цифр (0 <= число < 10) без ведущих нулей. Мистер Агоджи, который не очень хорошо разбирается в числах и строках, просит вашей помощи.

Формат ввода

Первая строка входных данных будет содержать T, количество тестовых случаев, 1 <= T <= 100. Для каждого тестового примера в отдельной строке будет перетасованная строка s.

1 <= s.length <= 100000

Выходной формат

Для каждого теста в новой строке наименьшее специальное число находится в строковом формате. Несколько замечаний по поводу вывода: Перетасованная строка всегда может быть преобразована хотя бы в одну допустимую специальную строку. Перемешанная строка будет содержать только маленькие буквы английского алфавита. Если перетасованная строка содержит только нули, следует вывести «0».

Подход:

1. создать карту цифр в слова
2. создать карту частот символов из входной строки
3. Пройдите все цифры от 0 до 9 и посмотрите, сколько чисел представлено в строке. сохранить его в словаре digit_freq
4. отсортировать все числа в digit_freq и создать строку из этого
5. Есть несколько крайних случаев, о которых нам нужно позаботиться. Если все равны нулю, верните 0. Еще один пограничный случай: мы не можем оставить 0 перед позициями строки результата. мы можем оставить все нули после первой ненулевой цифры, чтобы создать наименьшее число в соответствии с требованием.

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))

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;
    }
}

Пожалуйста, подпишитесь на меня на Medium и Youtube , если вы нашли это объяснение полезным.

Помогите алгоритму найти эту статью другим пользователям, нажав на хлоп. :)