检查字符串的所有字符是否包含相同的次数

Question

我正在处理以下问题陈述：如果字符串的所有字符出现相同的次数，则该字符串是有效的。如果我们可以只删除字符串中 1 个索引处的 1 个字符，并且剩余的字符将出现相同的次数，这也是有效的。给定一个字符串 s，判断它是否有效。如果是，返回YES，否则返回NO。例如，如果s=abc，它是一个有效的字符串，因为频率是 {a:1,b:1,c:1}。所以是s=abcc因为我们可以删除一个c并且在剩余的字符串中每个字符都有 1 个。s=abccc 但是，如果字符串无效，因为我们只能删除 1 次出现 c。这将留下{a:1,b:1,c:2}.我想出了下面的代码，但它没有按预期工作，并且在此输入上失败abcdefghhgfedecba。它正在打印“NO”，但该输入应该是“YES”。private static String isValid(String s) {    if (s == null || s.equals("")) {        return "NO";    }    Map<Character, Integer> frequencies = new HashMap<>();    for (char ch : s.toLowerCase().toCharArray())        frequencies.put(ch, frequencies.getOrDefault(ch, 0) + 1);    int count = 0;    // Iterating over values only    for (Integer value : frequencies.values()) {        if (value == 2) {            count++;        }    }    if (count >= 1) {        return "YES";    }    return "NO";}我在这里做什么错了？做到这一点的最佳和有效方法是什么？

Answer 1

下面的代码工作正常。我在这里做的是将每个字符的频率存储在一个数组中，然后将其转换为列表，因为我们将需要稍后的时间点。接下来我将列表转换为设置并从中删除零，因为列表中将存在与输入字符串中不存在的字符相对应的零。如果 set 在删除零后只有一个元素意味着所有元素都具有相同的频率，因此返回 true。如果 set 有两个以上的元素意味着我们无法通过在一个地方删除一个字符来使其成为有效字符串，因此返回 false. 现在，如果 set 有两个值，我们从 set 中取最小值和最大值。如果有一个频率是第一个 if 条件的字符，我们可以使它有效。现在第二个条件是，如果差异 b/w max 和 min 为 1 并且 max 只有一个频率，那么我们可以从 max 中删除一个字符并使其有效。

static String isValid(String s) {

        Integer arr[] = new Integer[26];

        Arrays.fill(arr, 0);

        //fill the frequency of every character in array arr

        for (int i = 0; i < s.length(); i++) {

            arr[s.charAt(i) - 97]++;

        }

        //convert array to list of integer     

        List<Integer> arrList = Arrays.asList(arr);

        //convert list to set and remove zero bcos zero correspond to char that is not present

        HashSet<Integer> set = new HashSet<Integer>(arrList);

        set.remove(new Integer(0));

        int len = set.size();

        // if size==1 means all freq are same

        if (len == 1)

            return "YES";

        else if (len == 2) {

            List<Integer> list = new ArrayList<>(set);

            int x = list.get(0);

            int y = list.get(1);

            int max = (x > y) ? x : y;

            int min = (x < y) ? x : y;

             // if min elemnnt has value one and freuency one

            if (Collections.frequency(arrList, min) == 1 && min == 1) {

                return "YES";

            }

          //if max-min==1 and there are only one elemnt with value=max      

         else if (max - min == 1) {

                if ((Collections.frequency(arrList, max) == 1)) {

                    return "YES";

                } else {

                    return "NO";

                }

            } 

          // if no of element is more than

          else {

                return "NO";

            }

        } else

            return "NO";

    }

Answer 2

计算频率是正确的想法，尽管我不确定您为什么要检查地图中的值是否为2. 一旦我计算了这些频率，我将创建一个具有每个频率的字符数的反向映射，然后：

1. 如果地图的大小为 1，则表示所有字符具有相同的频率 - 字符串有效。

2. 如果集合的大小为 2：

• 如果最小频率为 1 并且只有一个字符具有该频率，则该字符串有效，因为可以简单地删除该字符

• 如果最小频率比最大频率小 1，并且只有一个字符具有最大频率，则该字符串有效，因为可以删除该字符。

3. 在任何其他情况下，该字符串将无效。

private static boolean isValid(String s) {

    TreeMap<Long, Long> frequencyCounts =

            s.chars()

             .boxed()

             // Frequency map

             .collect(Collectors.groupingBy(Function.identity(), Collectors.counting()))

             .values()

             .stream()

             // Frequency of frequencies map

             .collect(Collectors.groupingBy

                                 (Function.identity(),

                                  TreeMap::new,

                                  Collectors.counting()));

    if (frequencyCounts.size() == 1) {

        return true;

    }

    if (frequencyCounts.size() == 2) {

        Iterator<Map.Entry<Long, Long>> iter = frequencyCounts.entrySet().iterator();

        Map.Entry<Long, Long> minEntry = iter.next();

        long minFrequency = minEntry.getKey();

        long numMinFrequency = minEntry.getValue();

        if (minFrequency == 1L && numMinFrequency == 1L) {

            return true;

        }

        Map.Entry<Long, Long> maxEntry = iter.next();

        long maxFrequency = maxEntry.getKey();

        long numMaxFrequency = maxEntry.getValue();

        if (numMaxFrequency == 1L && maxFrequency == minFrequency + 1L) {

            return true;

        }

    }

    return false;

}

编辑：

为了回答评论中的问题，频率图和“频率频率”图也可以用 Java 7 的语法构造，尽管它可能不那么优雅：

Map<Character, Long> frequencies = new HashMap<>();

for (int i = 0; i < s.length(); ++i) {

    char c = s.charAt(i);

    if (frequencies.containsKey(c)) {

        frequencies.put(c, frequencies.get(c) + 1L);

    } else {

        frequencies.put(c, 1L);

    }

}

TreeMap<Long, Long> frequencyCounts = new TreeMap<>();

for (Long freq : frequencies.values()) {

    if (frequencyCounts.containsKey(freq)) {

        frequencyCounts.put(freq, frequencyCounts.get(freq) + 1L);

    } else {

        frequencyCounts.put(freq, 1L);

    }

}