Leetcode 1737. Change Minimum Characters to Satisfy One of Three Conditions

Problem Explanation

You are given two strings a and b consisting of lowercase letters. Your goal is to make one of the following three conditions true by changing the characters in the strings with a minimal number of operations:

1. Every letter in a is strictly less than every letter in b in the alphabet.
2. Every letter in b is strictly less than every letter in a in the alphabet.
3. Both a and b consist of only one distinct letter.

Your task is to find the minimum number of operations needed to achieve this goal.

Example Walkthrough

Let's walk through the first example provided:

1a = "aba"
2b = "caa"

• To satisfy condition 1, we can change b to "ccc" in 2 operations. All letters in "aba" are less than the letters in "ccc".
• To satisfy condition 2, we can change a to "bbb" and b to "aaa" in 3 operations. All letters in "aaa" are less than the letters in "bbb".
• To satisfy condition 3, we can change a to "aaa" and b to "aaa" in 2 operations.

The best solution is achieved in 2 operations by satisfying either condition 1 or condition 3.

Solution Approach

We can solve this problem using a few simple steps and data structures:

1. Loop through both strings a and b and count the occurrences of each character.
2. Initialize variables prevA and prevB for counting the number of characters less than or equal to 'c' in each string.
3. Loop through each character 'c' in the alphabet.
   • Calculate the number of operations required to satisfy each condition.
   • Select the minimum number of operations from the previous conditions.
   • Update prevA and prevB.

The minimum number of operations required for one of the conditions will be our final answer.

Now let's implement the algorithm in Python, Java, JavaScript, C++, and C#.

Python Solution

1class Solution:
2    def minCharacters(self, a: str, b: str) -> int:
3        m = len(a)
4        n = len(b)
5        countA = [0] * 128
6        countB = [0] * 128
7
8        for c in a:
9            countA[ord(c)] += 1
10
11        for c in b:
12            countB[ord(c)] += 1
13
14        ans = float('inf')
15        prevA = 0
16        prevB = 0
17
18        for c in range(ord('a'), ord('z') + 1):
19            char = chr(c)
20            ans = min(ans, m + n - countA[ord(char)] - countB[ord(char)])
21            if c > ord('a'):
22                ans = min(ans, m - prevA + prevB, n - prevB + prevA)
23            prevA += countA[ord(char)]
24            prevB += countB[ord(char)]
25
26        return ans

Java Solution

1import java.util.*;
2
3class Solution {
4    public int minCharacters(String a, String b) {
5        int m = a.length();
6        int n = b.length();
7        int[] countA = new int[128];
8        int[] countB = new int[128];
9
10        for (char c : a.toCharArray()) {
11            countA[c]++;
12        }
13
14        for (char c : b.toCharArray()) {
15            countB[c]++;
16        }
17
18        int ans = Integer.MAX_VALUE;
19        int prevA = 0;
20        int prevB = 0;
21
22        for (char c = 'a'; c <= 'z'; c++) {
23            ans = Math.min(ans, m + n - countA[c] - countB[c]);
24            if (c > 'a') {
25                ans = Math.min(ans, Math.min(m - prevA + prevB, n - prevB + prevA));
26            }
27            prevA += countA[c];
28            prevB += countB[c];
29        }
30
31        return ans;
32    }
33}

JavaScript Solution

1class Solution {
2    minCharacters(a, b) {
3        const m = a.length;
4        const n = b.length;
5        const countA = new Array(128).fill(0);
6        const countB = new Array(128).fill(0);
7
8        for (const c of a) {
9            countA[c.charCodeAt()]++;
10        }
11
12        for (const c of b) {
13            countB[c.charCodeAt()]++;
14        }
15
16        let ans = Infinity;
17        let prevA = 0;
18        let prevB = 0;
19
20        for (let c = 'a'.charCodeAt(); c <= 'z'.charCodeAt(); c++) {
21            const char = String.fromCharCode(c);
22            ans = Math.min(ans, m + n - countA[char.charCodeAt()] - countB[char.charCodeAt()]);
23            if (c > 'a'.charCodeAt()) {
24                ans = Math.min(ans, m - prevA + prevB, n - prevB + prevA);
25            }
26            prevA += countA[char.charCodeAt()];
27            prevB += countB[char.charCodeAt()];
28        }
29
30        return ans;
31    }
32}

C++ Solution

1#include <vector>
2#include <string>
3#include <algorithm>
4using namespace std;
5
6class Solution {
7public:
8    int minCharacters(string a, string b) {
9        int m = a.length();
10        int n = b.length();
11        vector<int> countA(128, 0);
12        vector<int> countB(128, 0);
13
14        for (const char& c : a) ++countA[c];
15        for (const char& c : b) ++countB[c];
16
17        int ans = INT_MAX;
18        int prevA = 0;
19        int prevB = 0;
20
21        for (char c = 'a'; c <= 'z'; ++c) {
22            ans = min(ans, m + n - countA[c] - countB[c]);
23            if (c > 'a')
24                ans = min({ans, m - prevA + prevB, n - prevB + prevA});
25            prevA += countA[c];
26            prevB += countB[c];
27        }
28
29        return ans;
30    }
31};

C# Solution

1using System;
2using System.Collections.Generic;
3
4public class Solution {
5    public int MinCharacters(string a, string b) {
6        int m = a.Length;
7        int n = b.Length;
8        int[] countA = new int[128];
9        int[] countB = new int[128];
10
11        foreach (char c in a) {
12            countA[c]++;
13        }
14
15        foreach (char c in b) {
16            countB[c]++;
17        }
18
19        int ans = int.MaxValue;
20        int prevA = 0;
21        int prevB = 0;
22
23        for (char c = 'a'; c <= 'z'; c++) {
24            ans = Math.Min(ans, m + n - countA[c] - countB[c]);
25            if (c > 'a') {
26                ans = Math.Min(ans, Math.Min(m - prevA + prevB, n - prevB + prevA));
27            }
28            prevA += countA[c];
29            prevB += countB[c];
30        }
31
32        return ans;
33    }
34}

Summary

We learned to minimize the operations needed to reach one of three given conditions between two strings, and described the solution approach for this problem. We then implemented and explained the solution in Python, Java, JavaScript, C++, and C#.

In summary, we must compare the counts of each character in the strings for each given condition, then select the best solution that requires the least number of operations to return as our final answer. This solution ensures the minimal number of operations necessary to achieve one of the required conditions.