Leetcode Weekly Contest 225 (Change Minimum Characters to Satisfy One of Three Conditions)

#career #programming #computerscience #algorithms

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 ・ Feb 6, 2021 ・
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 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).

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 and b 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.


	public class LC1737 {
	class Solution {
	public int minCharacters(String a, String b) {
	int ans = Integer.MAX_VALUE;

	//WE call the make method for first two conditions. First call makes a smaller than b and second one makes b smaller than a.
	ans = Math.min(make(a,b),make(b,a));

	//This is for the 3rd conditions. We count the steps to make the strings contain only one distinct character.
	for(char ch='a';ch<='z';ch++){

	int total = a.length() + b.length();

	for(char c:a.toCharArray())
	if(c==ch)
	total--;
	for(char c:b.toCharArray())
	if(c==ch)
	total--;

	ans = Math.min(total,ans);

	}


	return ans;
	}

	//This method checks for the first two conditions
	//For given string a and b, we try to make a smaller than b . We count the no of steps needed to make a smaller than b . We return the minimum value for it.
	public int make(String a, String b){

	int local = Integer.MAX_VALUE;

	for(char ch='b';ch<='z';ch++){

	int temp = 0;
	for(char c:a.toCharArray()){
	if(c>=ch)
	temp++;
	}

	for(char c:b.toCharArray()){
	if(c<ch)
	temp++;
	}
	local = Math.min(local,temp);

	}

	return local;
	}

	}
	}

view raw LC1737.java hosted with ❤ by GitHub

	class LC1737 {
	public:
	//make a less than b
	int make(string a, string b)
	{
	int local = INT_MAX;
	for(char ch='b'; ch<='z'; ch++)
	{
	//all characters in a are < ch
	//all characters in b are >= ch
	int temp = 0;
	for(char c:a)if(!(c<ch))temp++;
	for(char c:b)if(!(c>=ch))temp++;
	local = min(local, temp);
	}
	return local;
	}
	int minCharacters(string a, string b) {
	int ans = INT_MAX;
	ans = min(make(a,b), make(b,a));
	for(char ch='a'; ch<='z'; ch++)
	{
	int total = a.length()+b.length();
	for(char c : a) if(c == ch) total--;
	for(char c : b) if(c == ch) total--;
	ans = min(ans, total);
	}
	return ans;
	}
	};