package y2019.Algorithm.array;

import java.util.*;

/**
 * @ProjectName: cutter-point
 * @Package: y2019.Algorithm.array
 * @ClassName: CommonChars
 * @Author: xiaof
 * @Description: 1002. Find Common Characters
 * Given an array A of strings made only from lowercase letters, return a list of all characters that show up in all strings
 * within the list (including duplicates).
 * For example, if a character occurs 3 times in all strings but not 4 times, you need to include that character three times
 * in the final answer.
 * You may return the answer in any order.
 *
 * Input: ["bella","label","roller"]
 * Output: ["e","l","l"]
 *
 * @Date: 2019/7/4 11:07
 * @Version: 1.0
 */
public class CommonChars {

    public List<String> solution(String[] A) {
        List<String> result = new ArrayList<>();
        int[] nums = new int[26]; //英文一共26个字符，并且是小写的
        Arrays.fill(nums, Integer.MAX_VALUE);
        //遍历所有的字符，根据小标放入集合中
        for(String aTemp : A) {
            //依次遍历所有字符
            char tempC[] = aTemp.toCharArray();
            int[] cnt = new int[26];
            //第一次统计每个单词中出现的次数
            for(int j = 0; j < tempC.length; ++j) {
                cnt[tempC[j] - 'a']++;
            }
            //第二次我们过滤掉，每二个单词中出现的最小次数，比如第一个单词出现10次，但是第二个单词出现1次，那么都出现的次数也就是1次
            for(int i = 0; i < nums.length; ++i) {
                nums[i] = Math.min(nums[i], cnt[i]);
            }
        }

        //最后统计结果
        for(int i = 0; i < nums.length; ++i) {
            for(int j = 0; j < nums[i]; ++j) {
                //如果出现多处，那么放入多处
                result.add("" + (char) ('a' + i));
            }
        }

        //如果每个字符中都出现过，那么必须是3的倍数次
        return result;
    }


    public List<String> commonChars(String[] A) {
        List<String> ans = new ArrayList<>();
        int[] count = new int[26];
        Arrays.fill(count, Integer.MAX_VALUE);
        for (String str : A) {
            int[] cnt = new int[26];
            for (int i = 0; i < str.length(); ++i) { ++cnt[str.charAt(i) - 'a']; } // count each char's frequency in string str.
            for (int i = 0; i < 26; ++i) { count[i] = Math.min(cnt[i], count[i]); } // update minimum frequency.
        }
        for (char c = 'a'; c <= 'z'; ++c) {
            while (count[c - 'a']-- > 0) { ans.add("" + c); }
        }
        return ans;
    }

    public static void main(String args[]) {
        String as[] = {"bella","label","roller"};
        CommonChars fuc = new CommonChars();
        System.out.println(fuc.solution(as));
    }
}