Formatted question description: https://leetcode.ca/all/1737.html

1737. Change Minimum Characters to Satisfy One of Three Conditions

Level

Medium

Description

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 <= 10^5
• a and b consist only of lowercase letters.

Solution

For the first two conditions, calculate the number of occurrences of each letter in each of the strings a and b respectively, and calculate the prefix sums and the suffix sums respectively. Then loop over the number of occurrences. For each i from 0 to 24, calculate the number of operations to change letters in a to letters in indices 0 to i and change letters in b to letters in indices i + 1 to 25, and calculate the number of operations to change letters in b to letters in indices 0 to i and change letters in a to letters in indices i + 1 to 25. Maintain the minimum number of operations during the process, which is the minimum number of operations for conditions 1 and 2.

For condition 3, obtain the maximum occurrence of letters in a and b respectively, and the remaining letters need to be changed to such a letter for each string.

Finally, return the minimum number of operations among three conditions.

class Solution {
    public int minCharacters(String a, String b) {
        int[] aCounts = new int[26];
        int[] bCounts = new int[26];
        int aMaxCount = 0, bMaxCount = 0;
        int aLength = a.length(), bLength = b.length();
        for (int i = 0; i < aLength; i++) {
            char c = a.charAt(i);
            aCounts[c - 'a']++;
            aMaxCount = Math.max(aMaxCount, aCounts[c - 'a']);
        }
        for (int i = 0; i < bLength; i++) {
            char c = b.charAt(i);
            bCounts[c - 'a']++;
            bMaxCount = Math.max(bMaxCount, bCounts[c - 'a']);
        }
        int[] aCountsPrefix = new int[26];
        int[] aCountsSuffix = new int[26];
        int[] bCountsPrefix = new int[26];
        int[] bCountsSuffix = new int[26];
        aCountsPrefix[0] = aCounts[0];
        bCountsPrefix[0] = bCounts[0];
        for (int i = 1; i < 26; i++) {
            aCountsPrefix[i] = aCountsPrefix[i - 1] + aCounts[i];
            bCountsPrefix[i] = bCountsPrefix[i - 1] + bCounts[i];
        }
        aCountsSuffix[25] = aCounts[25];
        bCountsSuffix[25] = bCounts[25];
        for (int i = 24; i >= 0; i--) {
            aCountsSuffix[i] = aCountsSuffix[i + 1] + aCounts[i];
            bCountsSuffix[i] = bCountsSuffix[i + 1] + bCounts[i];
        }
        int op1 = Integer.MAX_VALUE, op2 = Integer.MAX_VALUE;
        for (int i = 0; i < 25; i++) {
            int curOp1 = aLength - aCountsPrefix[i] + bLength - bCountsSuffix[i + 1];
            int curOp2 = aLength - aCountsSuffix[i + 1] + bLength - bCountsPrefix[i];
            op1 = Math.min(op1, curOp1);
            op2 = Math.min(op2, curOp2);
        }
        int op3 = aLength - aMaxCount + bLength - bMaxCount;
        return Math.min(Math.min(op1, op2), op3);
    }
}

All Problems

All Solutions