Максимальное количество N с использованием цифр M, таких что 2 и 5, а также 6 и 9 можно рассматривать как одно и то же соответственно.

Учитывая целое число N и целую строку M , задача состоит в том, чтобы найти общее количество, необходимое для получения N , используя цифры строки M. Кроме того, цифру 2 можно рассматривать как цифру 5 , а цифру 6 можно рассматривать как цифру 9 и наоборот, и каждая цифра из строки M может использоваться не более одного раза.

Примеры:

Input: N = 6, M = “245769”
Output: 2
Explanation: Digits 5 and 6 are used to form the number 56. iop[The digits 2 and 9 are used to form the number 56. As 2 is treated as 5 and 9 is treated as 6.

Input: N = 25, M = “55”
Output: 1

Подход: Данная проблема может быть решена с помощью хеширования. Выполните следующие шаги, чтобы решить проблему:

• Создайте пустую хэш-карту, скажем, карту для хранения частоты цифр данной строки M .
• Создайте переменную, скажем, len для хранения длины строки.
• Пройдите заданную строку S , используя переменную i и повторяйте до тех пор, пока значение i не станет меньше, чем len , и выполните следующие шаги:
  • Если символ S[i] равен '5' , то измените его на '2' .
  • Если символ S[i] равен '9' , то измените его на '6'.
  • Если символ присутствует в mymap , измените частоту как mymap.put(x, map.get(x)+1).
  • В противном случае вставьте символ в карту с частотой 1 как mymap.put(x, 1) .
  • После добавления частоты к карте увеличьте i и перейдите к следующей итерации.
• Создайте пустую хэш-карту, скажем, rems для хранения цифр числа N.
• Повторяйте, пока значение N не станет больше 0, и выполните следующие шаги:
  • Создайте переменную, скажем, rem , чтобы сохранить последнюю цифру N , используя оператор модуля как N%10 .
  • Если rem равно 5 , то измените его на 2 .
  • Если rem равно 9 , измените его на 6 .
  • Если rem присутствует в карте rems , то увеличьте частоту на 1 as rems.put(rem, rems.get(rem)+1) .
  • В противном случае вставьте его в карту rems как rems.put(rem, 1) .
  • Разделите N на 10.
• Создайте переменную, скажем, cnt , чтобы хранить максимальное число N , которое может быть сформировано с использованием заданных цифр строки M.
• Пройдите через карту rems и выполните следующие шаги:
  • Пусть каждый объект на карте есть ele.
  • Проверьте, присутствует ли ключ от ele в частотной карте строки mymap .
  • Если нет, возвращается 0 (Число N не может быть сформировано, если цифра из N отсутствует в строке M).
  • Рассчитайте количество , разделив частоту ключа в mymap на частоту в карте rems как mymap.get(key)/ele.getValue() .
  • Обновите минимальное значение из всех итераций в cnt .
• После выполнения вышеуказанных шагов выведите в качестве результата значение cnt .

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N)
Вспомогательное пространство: O(1)