- 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)