1737. Change Minimum Characters to Satisfy One of Three Conditions LeetCode Solution
In this guide, you will get 1737. Change Minimum Characters to Satisfy One of Three Conditions LeetCode Solution with the best time and space complexity. The solution to Change Minimum Characters to Satisfy One of Three Conditions 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 Change Minimum Characters to Satisfy One of Three Conditions
You are given two strings a and b that consist of lowercase letters. In one operation, you can change any character in a or b to any lowercase letter.
Your goal is to satisfy one of the following three conditions:
Every letter in a is strictly less than every letter in b in the alphabet.
Every letter in b is strictly less than every letter in a in the alphabet.
Both a and b consist of only one distinct letter.
Return the minimum number of operations needed to achieve your goal.
Example 1:
Input: a = “aba”, b = “caa”
Output: 2
Explanation: Consider the best way to make each condition true:
1) Change b to “ccc” in 2 operations, then every letter in a is less than every letter in b.
2) Change a to “bbb” and b to “aaa” in 3 operations, then every letter in b is less than every letter in a.
3) Change a to “aaa” and b to “aaa” in 2 operations, then a and b consist of one distinct letter.
The best way was done in 2 operations (either condition 1 or condition 3).
Input: a = “dabadd”, b = “cda”
Output: 3
Explanation: The best way is to make condition 1 true by changing b to “eee”.
Constraints:
1 <= a.length, b.length <= 105
a and b consist only of lowercase letters.
Complexity Analysis
Time Complexity: O(|\texttt{a}| + |\texttt{b}|)
Space Complexity: O(26) = O(1)
1737. Change Minimum Characters to Satisfy One of Three Conditions LeetCode Solution in C++
class Solution {
public:
int minCharacters(string a, string b) {
const int m = a.length();
const int n = b.length();
vector<int> countA(26);
vector<int> countB(26);
for (const char c : a)
++countA[c - 'a'];
for (const char c : b)
++countB[c - 'a'];
int ans = INT_MAX;
int prevA = 0; // the number of characters in a <= c
int prevB = 0; // the number of characters in b <= c
for (char c = 'a'; c <= 'z'; ++c) {
// the condition 3
ans = min(ans, m + n - countA[c - 'a'] - countB[c - 'a']);
// the conditions 1 and 2
if (c > 'a')
ans = min({ans, m - prevA + prevB, n - prevB + prevA});
prevA += countA[c - 'a'];
prevB += countB[c - 'a'];
}
return ans;
}
}; /* code provided by PROGIEZ */
1737. Change Minimum Characters to Satisfy One of Three Conditions LeetCode Solution in Java
class Solution {
public int minCharacters(String a, String b) {
final int m = a.length();
final int n = b.length();
int[] countA = new int[26];
int[] countB = new int[26];
for (final char c : a.toCharArray())
++countA[c - 'a'];
for (final char c : b.toCharArray())
++countB[c - 'a'];
int ans = Integer.MAX_VALUE;
int prevA = 0; // the number of characters in a <= c
int prevB = 0; // the number of characters in b <= c
for (char c = 'a'; c <= 'z'; ++c) {
// the condition 3
ans = Math.min(ans, m + n - countA[c - 'a'] - countB[c - 'a']);
// the conditions 1 and 2
if (c > 'a')
ans = Math.min(ans, Math.min(m - prevA + prevB, n - prevB + prevA));
prevA += countA[c - 'a'];
prevB += countB[c - 'a'];
}
return ans;
}
} // code provided by PROGIEZ
1737. Change Minimum Characters to Satisfy One of Three Conditions LeetCode Solution in Python
