重排字符形成目标字符串【LC2287】
You are given two 0-indexed strings s and target. You can take some letters from s and rearrange them to form new strings.
Return the maximum number of copies of target that can be formed by taking letters from s and rearranging them.
加油加油
- 思路：使用两个哈希表记录两个字符串中字符出现的次数，假设某个字符的在s和target中出现次数分别为a和b ，那么该字母可被重排的次数为⌊ a/ b ⌋ ，target可以被重排的次数为所有字母可被重排的最小值。
- 实现
class Solution { public int rearrangeCharacters(String s, String target) { int[] sCount = new int[26]; int[] tCount = new int[26]; for (char c : s.toCharArray()){ sCount[c - 'a']++; } for (char c : target.toCharArray()){ tCount[c - 'a']++; } int res = Integer.MAX_VALUE; for (int i = 0; i < 26; i++){ if (tCount[i] != 0){ res = Math.min(res, sCount[i] / tCount[i]); } } return res; } }
。复杂度
- 时间复杂度：O ( n + m + C )，n、m为字符串长度
- 空间复杂度：O(C)，C为字符集大小，本题中为26
