#3081

Medium

auto_awesomeGreedy choice plus invariant validation

LeetCode Problem Workspace

Replace Question Marks in String to Minimize Its Value

Minimize the cost of a string with '?' characters by replacing them with letters in lexicographical order while minimizing the cost function.

hash table string greedy sorting heap priority queue

Problem Statement

You are given a string s, where each character is either a lowercase English letter or a '?'. Your goal is to replace all '?' characters with lowercase letters to minimize the value of the string. The value of the string is determined by the sum of cost(i) for all indices i. For a string t, the cost(i) at an index i is the number of occurrences of t[i] in the substring t[0..i-1].

You need to find the lexicographically smallest string that minimizes the total cost. Specifically, you are tasked with replacing '?' characters in a way that ensures the resulting string has the minimal cost, while keeping the overall structure as lexicographically small as possible. Be mindful of the fact that cost(i) depends on previous occurrences of characters and will influence future choices.

Examples

Example 1

Input: s = "???"

Output: "abc"

In this example, we can replace the occurrences of '?' to make s equal to "abc" . For "abc" , cost(0) = 0 , cost(1) = 0 , and cost(2) = 0 . The value of "abc" is 0 . Some other modifications of s that have a value of 0 are "cba" , "abz" , and, "hey" . Among all of them, we choose the lexicographically smallest.

Example 2

Input: s = "a?a?"

Output: "abac"

In this example, the occurrences of '?' can be replaced to make s equal to "abac" . For "abac" , cost(0) = 0 , cost(1) = 0 , cost(2) = 1 , and cost(3) = 0 . The value of "abac" is 1 .

Constraints

1 <= s.length <= 105
s[i] is either a lowercase English letter or '?'.

Solution Approach

Greedy Choice

To minimize the cost, greedily replace each '?' with the lexicographically smallest valid character. This ensures that no extra penalties are incurred from previous choices while minimizing cost.

Invariant Validation

As you replace each '?' character, check that the cost is minimized by ensuring no previously chosen characters repeat excessively. This validation helps in maintaining a minimal cost across the entire string.

Efficient Counting with Hash Table

Use a hash table to track the frequency of characters already in the string. This allows efficient lookup and ensures that characters are selected based on their frequency, which directly affects the cost calculation.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time and space complexity depend on the approach you choose. A naive solution might lead to O(n^2) due to repeated counting. However, with efficient hashing and careful greedy choices, the complexity can be reduced to O(n).

What Interviewers Usually Probe

Does the candidate demonstrate understanding of greedy algorithms and their application to string problems?
Is the candidate able to explain how the cost function influences their decision-making process?
How effectively does the candidate use hash tables to minimize cost while ensuring lexicographical order?

Common Pitfalls or Variants

Common pitfalls

Misunderstanding the cost calculation and how previous characters influence the current cost.
Failing to consider the lexicographical order of the string while replacing '?' characters.
Overcomplicating the solution by not utilizing hash tables efficiently for counting character occurrences.

Follow-up variants

Change the problem to handle a larger character set, such as including uppercase letters or digits.
Introduce a limit on the number of distinct characters allowed in the string.
Allow multiple valid outputs with the same cost but ask for the lexicographically largest string.

FAQ

How can I minimize the cost of the string in the 'Replace Question Marks in String to Minimize Its Value' problem?

To minimize the cost, replace '?' with the smallest lexicographical character while maintaining invariant validation to ensure previous characters don't repeat excessively.

What is the time complexity of solving the 'Replace Question Marks in String to Minimize Its Value' problem?

The time complexity depends on the approach but can be optimized to O(n) by using a hash table for frequency counting and greedy character selection.

What is the role of the hash table in solving the 'Replace Question Marks in String to Minimize Its Value' problem?

A hash table tracks the frequency of characters already in the string, allowing efficient character replacement and ensuring minimal cost without excessive repetition.

Can there be multiple valid solutions for this problem?

Yes, there can be multiple valid solutions with the same minimum cost. However, the lexicographically smallest solution is preferred.

What is the greedy approach used in the 'Replace Question Marks in String to Minimize Its Value' problem?

The greedy approach involves choosing the lexicographically smallest valid character to replace '?' in each step, ensuring the minimal cost at each stage of the string.

terminal

Solution

Solution 1: Greedy + Priority Queue

According to the problem, we can find that if a letter $c$ appears $v$ times, then the score it contributes to the answer is $1 + 2 + \cdots + (v - 1) = \frac{v \times (v - 1)}{2}$. To make the answer as small as possible, we should replace the question marks with those letters that appear less frequently.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

class Solution:
    def minimizeStringValue(self, s: str) -> str:
        cnt = Counter(s)
        pq = [(cnt[c], c) for c in ascii_lowercase]
        heapify(pq)
        t = []
        for _ in range(s.count("?")):
            v, c = pq[0]
            t.append(c)
            heapreplace(pq, (v + 1, c))
        t.sort()
        cs = list(s)
        j = 0
        for i, c in enumerate(s):
            if c == "?":
                cs[i] = t[j]
                j += 1
        return "".join(cs)

Continue Practicing

#3085 minimum deletions to make string k special #3035 maximum palindromes after operations #3016 minimum number of pushes to type word ii