3081. Replace Question Marks in String to Minimize Its Value LeetCode Solution
In this guide, you will get 3081. Replace Question Marks in String to Minimize Its Value LeetCode Solution with the best time and space complexity. The solution to Replace Question Marks in String to Minimize Its Value problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Replace Question Marks in String to Minimize Its Value
You are given a string s. s[i] is either a lowercase English letter or ‘?’.
For a string t having length m containing only lowercase English letters, we define the function cost(i) for an index i as the number of characters equal to t[i] that appeared before it, i.e. in the range [0, i – 1].
The value of t is the sum of cost(i) for all indices i.
For example, for the string t = “aab”:
cost(0) = 0
cost(1) = 1
cost(2) = 0
Hence, the value of “aab” is 0 + 1 + 0 = 1.
Your task is to replace all occurrences of ‘?’ in s with any lowercase English letter so that the value of s is minimized.
Return a string denoting the modified string with replaced occurrences of ‘?’. If there are multiple strings resulting in the minimum value, return the lexicographically smallest one.
Input: s = “???”
Output: “abc”
Explanation: 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”
Explanation: 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 '?'.
Complexity Analysis
Time Complexity: O(\texttt{sort})
Space Complexity: O(n)
3081. Replace Question Marks in String to Minimize Its Value LeetCode Solution in C++
class Solution {
public:
string minimizeStringValue(string s) {
string ans;
vector<int> count(26);
vector<char> letters;
for (const char c : s)
if (c != '?')
++count[c - 'a'];
for (const char c : s) {
if (c != '?')
continue;
const char minFreqLetter = getMinFreqLetter(count);
letters.push_back(minFreqLetter);
++count[minFreqLetter - 'a'];
}
ranges::sort(letters);
int i = 0; // letters' index
for (const char c : s)
ans += c == '?' ? letters[i++] : c;
return ans;
}
private:
char getMinFreqLetter(const vector<int>& count) {
char minFreqLetter = 'a';
for (char c = 'b'; c <= 'z'; ++c)
if (count[c - 'a'] < count[minFreqLetter - 'a'])
minFreqLetter = c;
return minFreqLetter;
}
}; /* code provided by PROGIEZ */
3081. Replace Question Marks in String to Minimize Its Value LeetCode Solution in Java
class Solution {
public String minimizeStringValue(String s) {
StringBuilder sb = new StringBuilder();
int[] count = new int[26];
List<Character> letters = new ArrayList<>();
for (final char c : s.toCharArray())
if (c != '?')
++count[c - 'a'];
for (final char c : s.toCharArray()) {
if (c != '?')
continue;
final char minFreqLetter = getMinFreqLetter(count);
letters.add(minFreqLetter);
++count[minFreqLetter - 'a'];
}
Collections.sort(letters);
int i = 0; // letters' index
for (final char c : s.toCharArray())
sb.append(c == '?' ? letters.get(i++) : c);
return sb.toString();
}
private char getMinFreqLetter(int[] count) {
char minFreqLetter = 'a';
for (char c = 'b'; c <= 'z'; ++c)
if (count[c - 'a'] < count[minFreqLetter - 'a'])
minFreqLetter = c;
return minFreqLetter;
}
} // code provided by PROGIEZ
3081. Replace Question Marks in String to Minimize Its Value LeetCode Solution in Python
class Solution:
def minimizeStringValue(self, s: str) -> str:
ans = []
count = collections.Counter(s)
letters = []
del count['?']
def getMinFreqLetter(count: dict[str, int]) -> str:
minFreqLetter = 'a'
for c in string.ascii_lowercase:
if count[c] < count[minFreqLetter]:
minFreqLetter = c
return minFreqLetter
for c in s:
if c == '?':
minFreqLetter = getMinFreqLetter(count)
letters.append(minFreqLetter)
count[minFreqLetter] += 1
letters.sort()
i = 0 # letters' index
for c in s:
if c == '?':
ans.append(letters[i])
i += 1
else:
ans.append(c)
return ''.join(ans) # code by PROGIEZ
