 Change Minimum Characters to Satisfy One of Three Conditions
Motivation to learn algorithms
Solve Leetcode Problems and Get Offers From Your Dream Companies  by Nil Madhab  LeetCode Simplified  Medium
Nil Madhab γ» γ»
Medium
Problem Statement
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 inb
in the alphabet. 
Every letter in
b
is strictly less than every letter ina
in the alphabet. 
Both
a
andb
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).
Example 2:
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
andb
consist only of lowercase letters.
Solution
In this problem, we are given two strings and we have to make them satisfy one of the 3 conditions by a minimum number of operations. In one operation, we can change any character in either string to any lowercase number.
So we have to check all the 3 conditions. In the make method, we check for the first 2 conditions. We pass the two strings to this method, For a given string a
, we try to make it strictly smaller than b
. We do it by making string a
smaller than a particular character ch
and string b
bigger than the same character. We call this method twice, first to make a
smaller than b
and then b
smaller than a
.
For the third condition, we make it contain only one distinct character, by changing each character to a particular character ch. We count the total number of operations and compare it with the minimum. At last, we return the ansvariable.
The following are the Java and C++ code for this problem.
The code can be found in the following repository.
Thank You for reading and Follow this publication for more LeetCode problems!π
Top comments (0)