Skip to content

Latest commit

 

History

History
188 lines (153 loc) · 4.65 KB

File metadata and controls

188 lines (153 loc) · 4.65 KB

English Version

题目描述

给你两个下标从 0 开始的字符串 starget 。你可以从 s 取出一些字符并将其重排,得到若干新的字符串。

s 中取出字符并重新排列,返回可以形成 target最大 副本数。

 

示例 1:

输入:s = "ilovecodingonleetcode", target = "code"
输出:2
解释:
对于 "code" 的第 1 个副本,选取下标为 4 、5 、6 和 7 的字符。
对于 "code" 的第 2 个副本,选取下标为 17 、18 、19 和 20 的字符。
形成的字符串分别是 "ecod" 和 "code" ,都可以重排为 "code" 。
可以形成最多 2 个 "code" 的副本,所以返回 2 。

示例 2:

输入:s = "abcba", target = "abc"
输出:1
解释:
选取下标为 0 、1 和 2 的字符,可以形成 "abc" 的 1 个副本。 
可以形成最多 1 个 "abc" 的副本,所以返回 1 。
注意,尽管下标 3 和 4 分别有额外的 'a' 和 'b' ,但不能重用下标 2 处的 'c' ,所以无法形成 "abc" 的第 2 个副本。

示例 3:

输入:s = "abbaccaddaeea", target = "aaaaa"
输出:1
解释:
选取下标为 0 、3 、6 、9 和 12 的字符,可以形成 "aaaaa" 的 1 个副本。
可以形成最多 1 个 "aaaaa" 的副本,所以返回 1 。

 

提示:

  • 1 <= s.length <= 100
  • 1 <= target.length <= 10
  • starget 由小写英文字母组成

解法

Python3

class Solution:
    def rearrangeCharacters(self, s: str, target: str) -> int:
        cnt = Counter(s)
        cnt2 = Counter(target)
        ans = inf
        for c, v in cnt2.items():
            if cnt[c] < v:
                return 0
            ans = min(ans, cnt[c] // v)
        return ans

Java

class Solution {
    public int rearrangeCharacters(String s, String target) {
        int[] cnt1 = new int[26];
        int[] cnt2 = new int[26];
        for (char c : s.toCharArray()) {
            ++cnt1[c - 'a'];
        }
        for (char c : target.toCharArray()) {
            ++cnt2[c - 'a'];
        }
        int ans = 100;
        for (int i = 0; i < 26; ++i) {
            if (cnt2[i] > 0) {
                if (cnt1[i] < cnt2[i]) {
                    return 0;
                }
                ans = Math.min(ans, cnt1[i] / cnt2[i]);
            }
        }
        return ans;
    }
}

C++

class Solution {
public:
    int rearrangeCharacters(string s, string target) {
        vector<int> cnt1(26);
        vector<int> cnt2(26);
        for (char& c : s) ++cnt1[c - 'a'];
        for (char& c : target) ++cnt2[c - 'a'];
        int ans = 100;
        for (int i = 0; i < 26; ++i) {
            if (cnt2[i] <= 0) continue;
            if (cnt1[i] < cnt2[i]) return 0;
            ans = min(ans, cnt1[i] / cnt2[i]);
        }
        return ans;
    }
};

Go

func rearrangeCharacters(s string, target string) int {
	cnt1 := make([]int, 26)
	cnt2 := make([]int, 26)
	for _, c := range s {
		cnt1[c-'a']++
	}
	for _, c := range target {
		cnt2[c-'a']++
	}
	ans := 100
	for i, v := range cnt2 {
		if v <= 0 {
			continue
		}
		if cnt1[i] < v {
			return 0
		}
		ans = min(ans, cnt1[i]/v)
	}
	return ans
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

TypeScript

function rearrangeCharacters(s: string, target: string): number {
    let cnt1 = new Array(128).fill(0),
        cnt2 = new Array(128).fill(0);
    for (let i of target) {
        cnt1[i.charCodeAt(0)]++;
    }
    for (let i of s) {
        cnt2[i.charCodeAt(0)]++;
    }
    let ans = Infinity;
    for (let i = 0; i < 128; i++) {
        if (cnt1[i] === 0) continue;
        ans = Math.min(ans, Math.floor(cnt2[i] / cnt1[i]));
    }
    return ans === Infinity ? 0 : ans;
}

...