Smallest Divisible Digit Product II
<p>You are given a string <code>num</code> which represents a <strong>positive</strong> integer, and an integer <code>t</code>.</p>

<p>A number is called <strong>zero-free</strong> if <em>none</em> of its digits are 0.</p>

<p>Return a string representing the <strong>smallest</strong> <strong>zero-free</strong> number greater than or equal to <code>num</code> such that the <strong>product of its digits</strong> is divisible by <code>t</code>. If no such number exists, return <code>&quot;-1&quot;</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">num = &quot;1234&quot;, t = 256</span></p>

<p><strong>Output:</strong> <span class="example-io">&quot;1488&quot;</span></p>

<p><strong>Explanation:</strong></p>

<p>The smallest zero-free number that is greater than 1234 and has the product of its digits divisible by 256 is 1488, with the product of its digits equal to 256.</p>
</div>

<p><strong class="example">Example 2:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">num = &quot;12355&quot;, t = 50</span></p>

<p><strong>Output:</strong> <span class="example-io">&quot;12355&quot;</span></p>

<p><strong>Explanation:</strong></p>

<p>12355 is already zero-free and has the product of its digits divisible by 50, with the product of its digits equal to 150.</p>
</div>

<p><strong class="example">Example 3:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">num = &quot;11111&quot;, t = 26</span></p>

<p><strong>Output:</strong> <span class="example-io">&quot;-1&quot;</span></p>

<p><strong>Explanation:</strong></p>

<p>No number greater than 11111 has the product of its digits divisible by 26.</p>
</div>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>2 &lt;= num.length &lt;= 2 * 10<sup>5</sup></code></li>
	<li><code>num</code> consists only of digits in the range <code>[&#39;0&#39;, &#39;9&#39;]</code>.</li>
	<li><code>num</code> does not contain leading zeros.</li>
	<li><code>1 &lt;= t &lt;= 10<sup>14</sup></code></li>
</ul>
Greedy; Math; String; Backtracking; Number Theory
func smallestNumber(num string, t int64) string {
	primeCount, isDivisible := getPrimeCount(t)
	if !isDivisible {
		return "-1"
	}

	factorCount := getFactorCount(primeCount)
	if sumValues(factorCount) > len(num) {
		return construct(factorCount)
	}

	primeCountPrefix := getPrimeCountFromString(num)
	firstZeroIndex := strings.Index(num, "0")
	if firstZeroIndex == -1 {
		firstZeroIndex = len(num)
		if isSubset(primeCount, primeCountPrefix) {
			return num
		}
	}

	for i := len(num) - 1; i >= 0; i-- {
		d := int(num[i] - '0')
		primeCountPrefix = subtract(primeCountPrefix, kFactorCounts[d])
		spaceAfterThisDigit := len(num) - 1 - i
		if i > firstZeroIndex {
			continue
		}
		for biggerDigit := d + 1; biggerDigit < 10; biggerDigit++ {
			factorsAfterReplacement := getFactorCount(
				subtract(subtract(primeCount, primeCountPrefix), kFactorCounts[biggerDigit]),
			)
			if sumValues(factorsAfterReplacement) <= spaceAfterThisDigit {
				fillOnes := spaceAfterThisDigit - sumValues(factorsAfterReplacement)
				return num[:i] + strconv.Itoa(biggerDigit) + strings.Repeat("1", fillOnes) + construct(factorsAfterReplacement)
			}
		}
	}

	factorsAfterExtension := getFactorCount(primeCount)
	return strings.Repeat("1", len(num)+1-sumValues(factorsAfterExtension)) + construct(factorsAfterExtension)
}

var kFactorCounts = map[int]map[int]int{
	0: {}, 1: {}, 2: {2: 1}, 3: {3: 1}, 4: {2: 2},
	5: {5: 1}, 6: {2: 1, 3: 1}, 7: {7: 1}, 8: {2: 3}, 9: {3: 2},
}

func getPrimeCount(t int64) (map[int]int, bool) {
	count := map[int]int{2: 0, 3: 0, 5: 0, 7: 0}
	for _, prime := range []int{2, 3, 5, 7} {
		for t%int64(prime) == 0 {
			t /= int64(prime)
			count[prime]++
		}
	}
	return count, t == 1
}

func getPrimeCountFromString(num string) map[int]int {
	count := map[int]int{2: 0, 3: 0, 5: 0, 7: 0}
	for _, d := range num {
		for prime, freq := range kFactorCounts[int(d-'0')] {
			count[prime] += freq
		}
	}
	return count
}

func getFactorCount(count map[int]int) map[int]int {
	res := map[int]int{}
	count8 := count[2] / 3
	remaining2 := count[2] % 3
	count9 := count[3] / 2
	count3 := count[3] % 2
	count4 := remaining2 / 2
	count2 := remaining2 % 2
	count6 := 0
	if count2 == 1 && count3 == 1 {
		count2, count3 = 0, 0
		count6 = 1
	}
	if count3 == 1 && count4 == 1 {
		count2 = 1
		count6 = 1
		count3, count4 = 0, 0
	}
	res[2] = count2
	res[3] = count3
	res[4] = count4
	res[5] = count[5]
	res[6] = count6
	res[7] = count[7]
	res[8] = count8
	res[9] = count9
	return res
}

func construct(factors map[int]int) string {
	var res strings.Builder
	for digit := 2; digit < 10; digit++ {
		res.WriteString(strings.Repeat(strconv.Itoa(digit), factors[digit]))
	}
	return res.String()
}

func isSubset(a, b map[int]int) bool {
	for key, value := range a {
		if b[key] < value {
			return false
		}
	}
	return true
}

func subtract(a, b map[int]int) map[int]int {
	res := make(map[int]int, len(a))
	for k, v := range a {
		res[k] = v
	}
	for k, v := range b {
		res[k] = max(0, res[k]-v)
	}
	return res
}

func sumValues(count map[int]int) int {
	sum := 0
	for _, v := range count {
		sum += v
	}
	return sum
}
