<p>You are given a string <code>s</code>. <code>s[i]</code> is either a lowercase English letter or <code>&#39;?&#39;</code>.</p>

<p>For a string <code>t</code> having length <code>m</code> containing <strong>only</strong> lowercase English letters, we define the function <code>cost(i)</code> for an index <code>i</code>&nbsp;as the number of characters <strong>equal</strong> to <code>t[i]</code>&nbsp;that appeared before it, i.e. in the range <code>[0, i - 1]</code>.</p>

<p>The <strong>value</strong> of <code>t</code> is the <strong>sum</strong> of <code>cost(i)</code> for all indices <code>i</code>.</p>

<p>For example, for the string <code>t = &quot;aab&quot;</code>:</p>

<ul>
	<li><code>cost(0) = 0</code></li>
	<li><code>cost(1) = 1</code></li>
	<li><code>cost(2) = 0</code></li>
	<li>Hence, the value of <code>&quot;aab&quot;</code> is <code>0 + 1 + 0 = 1</code>.</li>
</ul>

<p>Your task is to <strong>replace all</strong> occurrences of <code>&#39;?&#39;</code> in <code>s</code> with any lowercase English letter so that the <strong>value</strong> of <code>s</code> is <strong>minimized</strong>.</p>

<p>Return <em>a string denoting the modified string with replaced occurrences of </em><code>&#39;?&#39;</code><em>. If there are multiple strings resulting in the <strong>minimum value</strong>, return the <span data-keyword="lexicographically-smaller-string">lexicographically smallest</span> one.</em></p>

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

<div class="example-block" style="border-color: var(--border-tertiary); border-left-width: 2px; color: var(--text-secondary); font-size: .875rem; margin-bottom: 1rem; margin-top: 1rem; overflow: visible; padding-left: 1rem;">
<p><strong>Input: </strong> <span class="example-io" style="font-family: Menlo,sans-serif; font-size: 0.85rem;"> s = &quot;???&quot; </span></p>

<p><strong>Output: </strong> <span class="example-io" style="font-family: Menlo,sans-serif; font-size: 0.85rem;"> &quot;abc&quot; </span></p>

<p><strong>Explanation: </strong> In this example, we can replace the occurrences of <code>&#39;?&#39;</code> to make <code>s</code> equal to <code>&quot;abc&quot;</code>.</p>

<p>For <code>&quot;abc&quot;</code>, <code>cost(0) = 0</code>, <code>cost(1) = 0</code>, and <code>cost(2) = 0</code>.</p>

<p>The value of <code>&quot;abc&quot;</code> is <code>0</code>.</p>

<p>Some other modifications of <code>s</code> that have a value of <code>0</code> are <code>&quot;cba&quot;</code>, <code>&quot;abz&quot;</code>, and, <code>&quot;hey&quot;</code>.</p>

<p>Among all of them, we choose the lexicographically smallest.</p>
</div>

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

<div class="example-block" style="border-color: var(--border-tertiary); border-left-width: 2px; color: var(--text-secondary); font-size: .875rem; margin-bottom: 1rem; margin-top: 1rem; overflow: visible; padding-left: 1rem;">
<p><strong>Input: </strong> <span class="example-io" style="font-family: Menlo,sans-serif; font-size: 0.85rem;">s = &quot;a?a?&quot;</span></p>

<p><strong>Output: </strong> <span class="example-io" style="font-family: Menlo,sans-serif; font-size: 0.85rem;">&quot;abac&quot;</span></p>

<p><strong>Explanation: </strong> In this example, the occurrences of <code>&#39;?&#39;</code> can be replaced to make <code>s</code> equal to <code>&quot;abac&quot;</code>.</p>

<p>For <code>&quot;abac&quot;</code>, <code>cost(0) = 0</code>, <code>cost(1) = 0</code>, <code>cost(2) = 1</code>, and <code>cost(3) = 0</code>.</p>

<p>The value of <code>&quot;abac&quot;</code> is&nbsp;<code>1</code>.</p>
</div>

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

<ul>
	<li><code>1 &lt;= s.length &lt;= 10<sup>5</sup></code></li>
	<li><code>s[i]</code> is either a lowercase English letter or <code>&#39;?&#39;</code>.</li>
</ul>

# Notes

# string s has either lowercase letter or ?

# if t is a string with only lowercase letters, cost(i) = the numer of same characters that appear before it
# value of t is the sum of costs

# t = "aab", cost would be [0, 1, 0] = 1

# replace all ? in s to minimize the cost, prioritize letters that appear earlier in the alphabet

# I'm thinking need to keep a hashmap counting strings
# also want to keep a stack of next available letters?

# might want to use a heap to fetch the string with the lowest cost

import heapq
class Solution:
    def minimizeStringValue(self, s: str) -> str:
        # [
        #     (-26, "a"),
        #     (-25, "b"),
        #     (-24, "c"),
        #     (-23, "d"),
        #     (-22, "e"),
        #     (-21, "f"),
        #     (-20, "g"),
        #     (-19, "h"),
        #     (-18, "i"),
        #     (-17, "j"),
        #     (-16, "k"),
        #     (-15, "l"),
        #     (-14, "m"),
        #     (-13, "n"),
        #     (-12, "o"),
        #     (-11, "p"),
        #     (-10, "q"),
        #     (-9, "r"),
        #     (-8, "s"),
        #     (-7, "t"),
        #     (-6, "u"),
        #     (-5, "v"),
        #     (-4, "w"),
        #     (-3, "x"),
        #     (-2, "y"),
        #     (-1, "z"),
        # ]

        # what if we do a pass calculating all the letter costs first
        # then we add them to a heap
        # then we go and replace the ?
        # adding letters impacts cost of other adds (probably fine, we can caluclate on the fly?)
        # the cost of each letter changes at each point in the string
        # you probably don't want to or need to do this, since you don't really care about the rest of the string at any point

        # because we know a letter will move up in the cost ranking at most one spot at a time, we could probably keep track of
        # the rank efficiently via swapping places in an array

        # lex_letters = ["a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z"]
        # letter_index = {c: i for i, c in enumerate(lex_letters)}
        
        # # list of [(cost, letter)]
        # costs = []
        
        # result = ""
        # for c in s:
        #     # letter already exists, update its cost (update costs in the dict, fast)
        #     if c != "?":
        #         found = False
        #         for i, cost in enumerate(costs):
        #             if cost[1] == c:
        #                 costs[i] = (cost[0] + 1, cost[1])
        #                 found = True
        #                 break
        #         if not found:
        #             costs.append((0, c))
        #         lex_letters[letter_index[c]] = None
        #         result += c
            
        #     # there's letters with 0 cost still left to choose from, choose one of those (pick a letter, fast)
        #     elif len(costs) < 26:
        #         for letter in lex_letters:
        #             if letter is not None:
        #                 costs.append((0, letter))
        #                 lex_letters[letter_index[letter]] = None
        #                 result += letter
        #                 break
            
        #     # all the letters are chosen, we need to choose the letter with the lowest current cost (heapify and heap push, slower)
        #     else:
        #         heapq.heapify(costs)
        #         cost, letter = heapq.heappop(costs)
        #         result += letter
        #         heapq.heappush(costs, (cost+1, letter))

        # return result
        

        # this doesn't work, the assumption about letters not impact future letters was wrong.

        # this leads me to think we might have to count the cost of each letter in a first pass, and then replace

        # a?a?
        # costs = [(2, a)]
        # 1 -> 3 cost increases in factorial, but I'm not sure it really matters, just minimize the use of each letter in the total string

        # now I'm thinking keep the heap with the special score scheme of ... _ _ where

        # first build a dict of counts, then calculate all the scores, then heapify, then replace

        # count existing letters
        # lex_letters = ["a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z"]
        # letter_counts = {letter: 0 for letter in lex_letters}
        # for c in s:
        #     if c != "?":
        #         letter_counts[c] += 1
        
        # # calculate scores
        # scores = []
        # for i, letter in enumerate(lex_letters):
        #     score = letter_counts[letter] * 100 + i
        #     scores.append((score, letter))
        
        # # replace letters
        # heapq.heapify(scores)
        # for c in s:
        #     if c != "?":
        #         result += c
        #         continue

        #     score, letter = heapq.heappop(scores)
        #     result += letter
        #     score += 100
        #     heapq.heappush(scores, (score, letter))

        # return result

        # nevermind, this doesn't work either b/c they actually want lexegraphic order through the whole string

        # count existing letters
        lex_letters = ["a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z"]
        letter_counts = {letter: 0 for letter in lex_letters}
        unknown_count = 0
        for c in s:
            if c != "?":
                letter_counts[c] += 1
            else:
                unknown_count += 1
        
        # calculate scores
        scores = []
        for i, letter in enumerate(lex_letters):
            score = letter_counts[letter] * 100 + i
            scores.append((score, letter))
        
        # get letters to use to replace
        heapq.heapify(scores)
        letters_to_use = []
        for _ in range(unknown_count):
            score, letter = heapq.heappop(scores)
            letters_to_use.append(letter)
            score += 100
            heapq.heappush(scores, (score, letter))
        
        # replace letters
        letters_to_use.sort()
        pointer = 0
        result = ""
        for c in s:
            if c != "?":
                result += c
            else:
                result += letters_to_use[pointer]
                pointer += 1

        return result

313