Leetcode 3081: Replace Question Marks in String to Minimize Its Value
You are given a string
s consisting of lowercase English letters and question marks (?). Your task is to replace all occurrences of ? with any lowercase English letter in such a way that the total cost of the resulting string is minimized. The cost of a string is the sum of how many times each character has appeared before its current position. If there are multiple solutions with the same minimal cost, return the lexicographically smallest one.Problem
Approach
Steps
Complexity
Input: The input consists of a string `s` of length `n`, where `1 <= n <= 10^5`, and each character is either a lowercase English letter or `?`.
Example: s = "a?a?"
Constraints:
• 1 <= s.length <= 10^5
• s[i] is either a lowercase English letter or '?'
Output: Return a string where all occurrences of '?' are replaced with lowercase English letters in a way that minimizes the total cost. If there are multiple strings with the same minimal cost, return the lexicographically smallest one.
Example: Output: "abac"
Constraints:
Goal: Minimize the cost of the resulting string by replacing '?' characters.
Steps:
• Iterate over the string and maintain a frequency count of the letters already seen.
• For each '?', select the smallest letter that has appeared the least number of times so far.
• Replace '?' with this letter and update the frequency count.
Goal: The string `s` must have a length between 1 and 10^5 and contain only lowercase English letters or '?'.
Steps:
• 1 <= s.length <= 10^5
• Each character in `s` is either a lowercase English letter or '?'
Assumptions:
• The string can be large, so the solution must be efficient.
• The string only contains lowercase English letters or '?' characters.
• Input: s = "a?a?"
• Explanation: In this case, replacing the '?' with 'b' and 'c' results in the string 'abac', which has a minimal cost of 1.
• Input: s = "???"
• Explanation: Replacing the '?' with 'a', 'b', and 'c' results in the string 'abc', which has a minimal cost of 0.
Approach: To solve this problem efficiently, we need to replace the '?' characters with the lexicographically smallest possible letters while ensuring that the resulting string has the minimal cost.
Observations:
• Replacing '?' with letters that minimize the cost requires tracking the frequency of each letter in the string.
• We need to ensure that we minimize the cost while maintaining the lexicographical order.
Steps:
• Iterate through the string and count the frequency of each character.
• For each '?', select the lexicographically smallest character that has the lowest frequency so far.
• Update the frequency after replacing '?' and continue.
Empty Inputs:
• If the string contains only '?', the solution will replace each '?' with the smallest unused letters.
Large Inputs:
• For strings with the maximum length, the solution should be optimized to run in O(n) time.
Special Values:
• Strings that already have distinct letters or no '?' should be handled correctly.
Constraints:
• The solution should handle strings up to 10^5 characters efficiently.
string minimizeStringValue(string s) {
vector<int> frq(26, 0), taken;
int n = s.size();
for(char c: s) if(c != '?') frq[c - 'a']++;
for(int i = 0; i < n; i++) {
if(s[i] != '?') continue;
int mn = 0;
for(int j = 0; j < 26; j++)
if(frq[j] < frq[mn]) mn = j;
taken.push_back(mn);
frq[mn]++;
}
sort(taken.begin(), taken.end());
int idx = 0;
for(int i = 0; i < n; i++) {
if(s[i] == '?')
s[i] = taken[idx++] + 'a';
}
return s;
}
1 : Function Definition
string minimizeStringValue(string s) {
Defines the function `minimizeStringValue` which takes a string `s` and returns a modified string where '?' characters are replaced with the lexicographically smallest characters.
2 : Variable Initialization
vector<int> frq(26, 0), taken;
Declares a vector `frq` to track the frequency of each letter ('a' to 'z') in the string `s`. The `taken` vector will store the indices of characters to replace '?' with.
3 : Size Calculation
int n = s.size();
Calculates the length of the string `s` and stores it in `n`.
4 : Frequency Count
for(char c: s) if(c != '?') frq[c - 'a']++;
Loops through the string `s`, counting the frequency of each non-'?' character and storing it in the `frq` vector.
5 : Loop Through String
for(int i = 0; i < n; i++) {
Begins a loop through the string `s` to process each character.
6 : Skip Non-'?' Characters
if(s[i] != '?') continue;
Skips the iteration if the current character is not a '?'.
7 : Find Minimum Frequency
int mn = 0;
Initializes `mn` to 0, which will track the index of the character with the smallest frequency.
8 : Find Smallest Frequency Character
for(int j = 0; j < 26; j++)
Loops through all 26 lowercase English letters to find the character with the smallest frequency in `frq`.
9 : Update Minimum Index
if(frq[j] < frq[mn]) mn = j;
Updates `mn` to the index `j` if the frequency of the character at index `j` is smaller than the current minimum frequency.
10 : Store Chosen Character
taken.push_back(mn);
Adds the index of the character with the smallest frequency to the `taken` vector.
11 : Update Frequency
frq[mn]++;
Increments the frequency of the character chosen in the previous step.
12 : Sort Taken Characters
sort(taken.begin(), taken.end());
Sorts the `taken` vector in ascending order, ensuring the characters are replaced lexicographically.
13 : Initialize Index
int idx = 0;
Initializes `idx` to 0, which will be used to track the index of the next character to place in the string.
14 : Replace '?' Characters
for(int i = 0; i < n; i++) {
Loops through the string `s` again to replace '?' characters with the chosen characters from the `taken` vector.
15 : Replace Character
if(s[i] == '?')
Checks if the current character is a '?' that needs to be replaced.
16 : Assign Smallest Character
s[i] = taken[idx++] + 'a';
Replaces the '?' character with the corresponding character from the `taken` vector and increments `idx`.
17 : Return Statement
return s;
Returns the modified string `s` with all '?' characters replaced.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: The solution iterates over the string once, making the time complexity O(n), where n is the length of the string.
Best Case: O(1)
Worst Case: O(1)
Description: The space complexity is O(1) since the frequency count array has a fixed size of 26 for the 26 lowercase English letters.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus