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

class Solution:
    def minimizeStringValue(self, s: str) -> str:
        # Approach 1: heap
        alphabet = ascii_lowercase
        # initialize counters and a default dictionary
        ctr, dic = Counter(s), defaultdict(int)  # 'ctr' counts frequencies of each char in 's'; 'dic' to store final counts for replacements
        qmarks = ctr['?']  # number of '?' characters in the string
        rep = lambda x, y: x.replace('?', y, dic[y] - ctr[y])  # function to replace '?' with the correct character based on frequency
        # create a min-heap based on the frequency of each character in the alphabet
        heap = list(map(lambda x: (ctr[x], x), alphabet))  # map each character to a tuple of its count and the character itself
        heapify(heap)  # transform the list into a heap to allow efficient retrieval of the minimum frequency element
        # allocate '?' replacements by assigning the least frequent characters
        for _ in range(qmarks):
            cost, ch = heappop(heap)  # pop the character with the smallest frequency
            heappush(heap, (cost + 1, ch))  # push it back with an increased frequency to reflect its use in replacing '?'
        # update the dictionary with the final frequency counts after all '?' have been replaced
        for cost, ch in heap: 
            dic[ch] = cost  # store the final frequency for each character after replacing all '?'
        # replace all '?' in the original string with the correct characters based on the updated dictionary
        return reduce(rep, alphabet, s)  # apply the replacement function across all characters in the alphabet



        # # Approach 2:
        # # initialize a frequency array for lowercase letters (a-z)
        # freq = [0] * 26  
        # temp = []  # list to store the characters replacing '?'
        # # calculate the frequency of each character in the string, excluding '?'
        # for c in s:
        #     if c != '?':
        #         freq[ord(c) - ord('a')] += 1  # increment the frequency for the current character
        # # iterate over the string to find and replace '?' characters
        # for ind in range(len(s)):
        #     if s[ind] != '?':
        #         continue  # skip non-'?' characters
        #     # find the character with the minimum frequency in the current state
        #     minFreq = sys.maxsize  # set to maximum possible value initially
        #     minFreqInd = 0  # index to track the character with minimum frequency
        #     # check all 26 lowercase letters to find the one with the lowest frequency
        #     for i in range(26):
        #         if minFreq > freq[i]:  # if the current character has a lower frequency
        #             minFreq = freq[i]  # update the minimum frequency
        #             minFreqInd = i  # update the index of the minimum frequency character
        #     # append the character with the minimum frequency to the temp list
        #     temp.append(chr(ord('a') + minFreqInd))
        #     freq[minFreqInd] += 1  # increment the frequency of the selected character
        # # sort the temp list to ensure lexicographical order
        # temp.sort()
        # # create a list from the string to allow modification
        # result = list(s)
        # j = 0  # index to track position in the temp list
        # # replace the '?' characters in the original string with sorted characters
        # for i in range(len(result)):
        #     if result[i] == '?':
        #         result[i] = temp[j]  # replace '?' with the corresponding character from temp
        #         j += 1  # move to the next character in temp
        # # convert the list back to a string and return the result
        # return ''.join(result)



        # # My approach: pass 156/548, does not account for frequency
        # # record the letters that exists
        # charSet = set()
        # # record the index of ?
        # questionMarkIndexes = []
        # for i in range(len(s)):
        #     char = s[i]
        #     if char == "?":
        #         questionMarkIndexes.append(i)
        #     else:
        #         charSet.add(char)
        # print(charSet)
        # print(questionMarkIndexes)
        # # filter out the available letters
        # option = deque()
        # for letter in string.ascii_lowercase:
        #     if letter not in charSet:
        #         option.append(letter)
        # print(option)
        # # convert the input string to list
        # output = list(s)
        # if len(option) >= len(questionMarkIndexes):
        #     # filled in the ? with letter that never appeared before
        #     for index in questionMarkIndexes:
        #         sub = option.popleft()
        #         output[index] = sub
        # else:
        #     # if all 26 letters exist, just filled in a to make it lexicographically the smallest
        #     for j in range(len(questionMarkIndexes)-1, -1, -1):
        #         sub = "a"
        #         if option:
        #             sub = option.pop()
        #         output[questionMarkIndexes[j]] = sub
        # return "".join(output)
226