【Day 35 】2022-05-05 - 1737. 满足三条件之一需改变的最少字符数

[azl397985856]

1737. 满足三条件之一需改变的最少字符数

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/change-minimum-characters-to-satisfy-one-of-three-conditions/

前置知识

• 计数
• 枚举

  题目描述

  
  给你两个字符串 a 和 b ，二者均由小写字母组成。一步操作中，你可以将 a 或 b 中的 任一字符 改变为 任一小写字母 。

操作的最终目标是满足下列三个条件 之一 ：

a 中的 每个字母 在字母表中 严格小于 b 中的 每个字母 。 b 中的 每个字母 在字母表中 严格小于 a 中的 每个字母 。 a 和 b 都 由 同一个 字母组成。 返回达成目标所需的 最少 操作数。

 

示例 1：

输入：a = "aba", b = "caa" 输出：2 解释：满足每个条件的最佳方案分别是： 1) 将 b 变为 "ccc"，2 次操作，满足 a 中的每个字母都小于 b 中的每个字母； 2) 将 a 变为 "bbb" 并将 b 变为 "aaa"，3 次操作，满足 b 中的每个字母都小于 a 中的每个字母； 3) 将 a 变为 "aaa" 并将 b 变为 "aaa"，2 次操作，满足 a 和 b 由同一个字母组成。 最佳的方案只需要 2 次操作（满足条件 1 或者条件 3）。 示例 2：

输入：a = "dabadd", b = "cda" 输出：3 解释：满足条件 1 的最佳方案是将 b 变为 "eee" 。  

提示：

1 <= a.length, b.length <= 105 a 和 b 只由小写字母组成

[ZacheryCao]

Code

class Solution:
    def minCharacters(self, a: str, b: str) -> int:
        A = [0]*26
        B = [0]*26
        for i in a:
            A[ord(i)-ord('a')] += 1
        for i in b:
            B[ord(i)-ord('a')] += 1
        ans = math.inf
        for i in range(26):
            ans = min(ans, len(a)+len(b)-A[i]-B[i])
        for i in range(1, 26):
            t1 = 0
            t2 = 0
            for j in range(i,26):
                t1 += A[j]
                t2 += B[j]
            for j in range(i):
                t1 += B[j]
                t2 += A[j]
            ans = min(ans, t1, t2)
        return ans

[maggiexie00]

def minCharacters(self, a: str, b: str) -> int:

    m, n = len(a), len(b)
    c1 = Counter(ord(c) - 97 for c in a)

    c2 = Counter(ord(c) - 97 for c in b)

    res = m + n - max((c1 + c2).values()) # condition 3
    for i in range(25):
        c1[i + 1] += c1[i]
        c2[i + 1] += c2[i]
        res = min(res, m - c1[i] + c2[i]) # condition 1
        res = min(res, n - c2[i] + c1[i]) # condition 2
    return res

[ZETAVI]

class Solution { public: int minCharacters(string a, string b) { int n = a.size(); int m = b.size(); int l[26] = {0}; int r[26] = {0}; for (auto &x : a) { l[x - 'a']++; } for (auto &x : b) { r[x - 'a']++; } int lSum = 0; int rSum = 0; int ans = n + m; for (int i = 0; i < 25; ++i) { lSum += l[i]; rSum += r[i]; ans = min(ans, min(min(n + m - l[i] - r[i], n - lSum + rSum), m - rSum + lSum)); } ans = min(ans, n + m - l[25] - r[25]); return ans; } };

[taojin1992]

/*
1 <= a.length, b.length <= 10^5
a and b consist only of lowercase letters.

Plan:
1. get the freq of each char in a and b
2. operation numbers taken to make a and b contain only 1 char -> one of them can be empty
3. operations to make "Every letter in b is strictly less than every letter in a in the alphabet".

get min 

Time: 
O(a.length() + b.length())

Space: O(26) -> O(1)

Test:
"a"
"abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyz"
*/

class Solution {
    public int minCharacters(String a, String b) {
        int[] counterA = new int[26];
        int[] counterB = new int[26];

        for (int i = 0; i < a.length(); i++) {
            counterA[a.charAt(i) - 'a']++;
        }
        for (int i = 0; i < b.length(); i++) {
            counterB[b.charAt(i) - 'a']++;
        }

        int len = Math.min(opNumSameChar(a, b, counterA, counterB), opNumAGreater(a, b, counterA, counterB));
        len = Math.min(len, opNumAGreater(b, a, counterB, counterA));

        return len;
    }

    // only keep 'a' in a, then we can only keep 'b', or 'c', or 'd'..., or 'z' in b
    // operations taken: 
    // delete 'b's, 'c's, 'd's, ...'z's in String a -> only keep 'a's 
    // + 
    // delete 'a's in b for sure
    // assume we keep 'b's in String b
    // delete 'c's, 'd's, ..., 'z's in String b

    // delete char 'a' in str a
    // delete char 

    // Every letter in b is strictly less than every letter in a in the alphabet.
    private int opNumAGreater(String a, String b, int[] counterA, int[] counterB) {
        int opNum = a.length() + b.length();

        // c = 0 won't ac here
        for (int c = 1; c < 26; c++) {
            int count = 0;
            //delete all chars < c in a
            for (int smaller = 0; smaller < c; smaller++) {
                count += counterA[smaller];
            }
            // delete all chars >= c in b
            for (int larger = c; larger < 26; larger++) {
                count += counterB[larger];
            }
            opNum = Math.min(opNum, count);
        }
        return opNum;
    }

    // a = "aba", b = "caa"
    // a:2, b:1
    // a:2, b:0, c:1
    // 3+3 - 2-2 = 2, rm b and c, only keep a
    // 3+3 - 1 - 0 = 5, rm "aa" in a, "caa" in b
    // 3+3 - 0 - 1 = , rm "aba" in a, rm "aa" in b
    // only keep a, b, c....try out, and get min
    // operation numbers taken to make a and b contain only 1 char -> one of them can be empty
    private int opNumSameChar(String a, String b, int[] counterA, int[] counterB) {
        int opNum = a.length() + b.length();
        for (int i = 0; i < 26; i++) {
            opNum = Math.min(opNum, a.length() + b.length() - counterA[i] - counterB[i]);
        }
        return opNum;
    }
}

[gitbingsun]

题目地址(1737. 满足三条件之一需改变的最少字符数)

https://leetcode-cn.com/problems/change-minimum-characters-to-satisfy-one-of-three-conditions/

题目描述

给你两个字符串 a 和 b ，二者均由小写字母组成。一步操作中，你可以将 a 或 b 中的 任一字符 改变为 任一小写字母 。

操作的最终目标是满足下列三个条件 之一 ：

a 中的 每个字母 在字母表中 严格小于 b 中的 每个字母 。
b 中的 每个字母 在字母表中 严格小于 a 中的 每个字母 。
a 和 b 都 由 同一个 字母组成。

返回达成目标所需的 最少 操作数。

 

示例 1：

输入：a = "aba", b = "caa"
输出：2
解释：满足每个条件的最佳方案分别是：
1) 将 b 变为 "ccc"，2 次操作，满足 a 中的每个字母都小于 b 中的每个字母；
2) 将 a 变为 "bbb" 并将 b 变为 "aaa"，3 次操作，满足 b 中的每个字母都小于 a 中的每个字母；
3) 将 a 变为 "aaa" 并将 b 变为 "aaa"，2 次操作，满足 a 和 b 由同一个字母组成。
最佳的方案只需要 2 次操作（满足条件 1 或者条件 3）。

示例 2：

输入：a = "dabadd", b = "cda"
输出：3
解释：满足条件 1 的最佳方案是将 b 变为 "eee" 。

提示：

1 <= a.length, b.length <= 105
a 和 b 只由小写字母组成

前置知识

枚举+计数

class Solution { public: int minCharacters(string a, string b) { int len1 = a.length(); int len2 = b.length();

    vector<int> acount(26,0);
    vector<int> bcount(26,0);

    for (auto i : a) {
        acount[i-'a']++;
    }
    for (auto i : b) {
        bcount[i-'a']++;
    }

    int ret=INT_MAX;
    for (int threshhold = 0; threshhold < 26; threshhold++) {
        //实现条件1 or 2
        if (threshhold!=0) {
            ret = min(ret, minChanges(threshhold, acount, bcount));
            ret = min(ret, minChanges(threshhold, bcount, acount));
        }

        //实现条件3
        int changes = 0;
        for (int j = 0; j < 26; j++) {
            if (j!=threshhold) {
                changes += acount[j];
                changes += bcount[j];
            }
        }
        ret = min(ret, changes);
    }
    return ret;
}

int minChanges(int threshhold, vector<int>& acount, vector<int>& bcount){
    // 在string a 把所有大于i的字母都改小
    int changes = 0; 
    for (int j = threshhold; j < 26; j++) {
        changes += acount[j];
    }

    // 在string b 把所有小于i的字母都改大
    for (int j = 0; j < threshhold; j++) {
        changes += bcount[j];
    }
    return changes;
}

};

**复杂度分析**

令 n 为数组长度。

- 时间复杂度：$O(n)$
- 空间复杂度：$O(n)$

[Jessie725]

Idea

Condition 1 and 2 are same. Try each letter from b to z to be the board, count the number of operations we need for 1. all char in string a should < board and 2. all char in string b should >= board Condition 3. Count the freq of char in two strings. the char with highest freq should be the distinct letter. The operation we need is a.length + b.length - highest freq

Code

class Solution {
    public int minCharacters(String a, String b) {
        return Math.min(condition2(a, b), Math.min(condition1(a, b), condition1(b, a)));
    }

    public int condition1(String a, String b) {
        int min = Integer.MAX_VALUE;
        for (int i = 1; i < 26; i++) { // start from b to z
            int change = 0;

            for (char c : a.toCharArray()) {
                if ((c - 'a') >= i) {
                    ++change;
                }
            }
            for (char c : b.toCharArray()) {
                if ((c - 'a') < i) {
                    ++change;
                }
            } 
            min = Math.min(min, change);
        }
        return min;
    }

    public int condition2(String a, String b) {
        int[] counter = new int[26];
        for (char c : a.toCharArray()) {
            counter[c - 'a']++;
        }
        for (char c : b.toCharArray()) {
            counter[c - 'a']++;
        }

        int max = 0;
        for (int i : counter) {
            max = Math.max(max, i);
        }
        return a.length() + b.length() - max;
    }
}