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

Question

我正在处理以下问题陈述:

A string is valid if all characters of the string appear the same number of times. It is also valid if we can remove just 1 character at 1 index in the string, and the remaining characters will occur the same number of times. Given a string s, determine if it is valid. If so, return YES, otherwise return NO.

For example, if s=abc, it is a valid string because frequencies are {a:1,b:1,c:1} . So is s=abcc because we can remove one c and have 1 of each character in the remaining string. If s=abccc however, the string is not valid as we can only remove 1 occurrence of c. That would leave character frequencies of {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

计算频率是正确的想法，尽管我不确定您为什么要检查 map 中的值是否为 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);
    }
}