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。它正在打印“否”，但对于该输入，它应该是“是”

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，并从中删除了零，因为列表中的零对应于输入字符串中不存在的字符。如果在移除零后设置只有on元素，则表示所有元素的频率相同，因此返回true。如果集合有两个以上的元素，则表示无法通过在一个位置删除一个字符来使其成为有效字符串，因此返回false。现在如果集合有两个值，我们从集合中取最小值和最大值。我们可以使它有效，如果有一个字符具有一个频率，这就是第一个条件。第二个条件是，如果最大值和最小值之差为一，最大值只有一个频率，那么我们可以从最大值中删除一个字符，使其有效

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);
    }
}

Answer 3

爪哇8

import java.util.*;
public class MyClass {
    public static void main(String args[]) {
        Scanner scan = new Scanner(System.in);
        System.out.println(isValid(scan.next()));

    }

    private static String isValid(String s) {
        if (s == null || s.equals("")) {
          return "NO";
        }

        // frequencies ( hashmap) character : frequency 
        // contains frequency of each character of given string input
        Map<Character, Integer> frequencies = new HashMap<>();
        for (char ch : s.toLowerCase().toCharArray())
          frequencies.put(ch, frequencies.getOrDefault(ch, 0) + 1);

        // freqTypesCount ( hashmap) 
        // frequency_type : number_of_chars_having this frequency_type 
        Map<Integer, Integer> freqTypesCount = new HashMap<>();
        for (int ch : frequencies.values())
          freqTypesCount.put(ch, freqTypesCount.getOrDefault(ch, 0) + 1);


        if( freqTypesCount.size() == 1){
            // it means all the chars of string occurs same number of time
            return "YES";
        }
        else if( freqTypesCount.size() > 2){
            // aaabbbbccdd
            // a : 3 b: 4 c:2 d:2  > {3:1, 4:1, 2:2}
            // we can't make this string a valid string just by deleting single char
            return "NO";
        }
        else{
            int valid_freq = Collections.max(freqTypesCount.entrySet(), Map.Entry.comparingByValue()).getKey(); 
            int deleted = 0;

            for (Map.Entry<Character, Integer> entry : frequencies.entrySet())
            { 
                int thisCharCount = entry.getValue();

                if(thisCharCount != valid_freq){

                    if(deleted == 0){
                        if(thisCharCount - 1 == valid_freq || thisCharCount - 1 == 0){
                            deleted += 1;
                        }
                        else{
                            return "NO";
                        }
                    }
                    else{
                         return "NO";
                    }
                }
            }

            return "YES" ;
        }
    }
}

python 3

from collections import Counter

inp_string = input()

def isValidStr( string):
    char_counter_dict = Counter( string)
    count_type_counter_dict = Counter(char_counter_dict.values())

    if len(count_type_counter_dict) == 1:
        return "YES"
    elif len(count_type_counter_dict) > 2:
        return "NO"
    else:
        valid_freq = count_type_counter_dict.most_common()[0][0]

        deleted = 0

        for char,count in char_counter_dict.items():

            if count != valid_freq:

                if deleted == 0:
                    if count - 1 == valid_freq or count - 1 == 0:
                        deleted += 1

                    else:
                        return "NO"

                else:
                    return "NO"


        return "YES"

print(isValidStr(inp_string))