1859. Change Minimum Characters To Satisfy One Of Three Conditions¶

Difficulty: Medium

1859. Change Minimum Characters to Satisfy One of Three Conditions

Medium

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⁵
a and b consist only of lowercase letters.

Solution¶

class Solution {
    public int minCharacters(String a, String b) {
        int n = a.length(), m = b.length();

        int op1 = calcDistinct(a, b);

        int freq1[] = new int[26], freq2[] = new int[26];
        for (int i = 0; i < n; i++)
            freq1[a.charAt(i) - 'a']++;
        for (int i = 0; i < m; i++)
            freq2[b.charAt(i) - 'a']++;

        int cx = 0, cy = 0;
        for (int i = 0; i < 25; i++) {
            cx += freq1[i];
            cy += freq2[i];
            op1 = Math.min(op1, Math.min(n - cx + cy, m - cy + cx));
        }
        return op1;
    }
    private int calcDistinct(String s, String t) {
        int n = s.length(), m = t.length();
        int freq1[] = new int[26], freq2[] = new int[26];
        for (int i = 0; i < n; i++)
            freq1[s.charAt(i) - 'a']++;
        for (int i = 0; i < m; i++)
            freq2[t.charAt(i) - 'a']++;
        int maxi1 = 0, maxi2 = 0;
        for (int i = 0; i < 26; i++) {
            maxi1 = Math.max(maxi1, freq1[i]);
            maxi2 = Math.max(maxi2, freq2[i]);
        }
        return n - maxi1 + m - maxi2;
    }
}

Complexity Analysis¶

Time Complexity: O(?)
Space Complexity: O(?)

Approach¶

Detailed explanation of the approach will be added here