В дополнение к ответу @JohnKugelman, вот что вы можете сделать.
Прежде всего, вы проходите свою строку дважды (с внутренним l oop), чтобы подсчитать вхождения, которые равны O ( п ^ 2). Вы уже нашли O (n) решение для этого
Map<Character, Integer> occurences = new HashMap<>();
s.chars()
.forEach(e-> occurences.put((char)e, occurences.getOrDefault((char)e, 0) + 1));
Теперь нам нужно найти простую итерацию, чтобы найти ответ.
Вот что мы знаем о "YES" падежи.
- Все буквы имеют одинаковую частоту, например: aabbccddeeff
- Все буквы имеют одинаковую частоту, но одна буква встречается 1 раз больше. Например: aabb ccddd
- Все буквы имеют одинаковую частоту, но одну букву с 1 вхождением. Например: aaaabbbbcccce
Итак, нам нужно go просмотреть значения нашей карты и подсчитать количество вхождений.
Сначала давайте возьмем наш итератор
Iterator<Map.Entry<Character, Integer>> iterator = occurences
.entrySet()
.iterator();
Затем выберите первое число в качестве «эталона» и определите переменную и число для первого различного значения
int benchmark = iterator.next().getValue();
int benchmarkCount = 1;
int firstDifferent = -1;
int differentCount = 0;
Перебирайте числа
while(iterator.hasNext()) {
int next = iterator.next().getValue();
if (next == benchmark) { // if the next number is same
benchmarkCount++; // just update our count
} else { // if it is different
// if we haven't found a different one yet or it is the same different value from earlier
if (firstDifferent == -1 || firstDifferent == next) {
firstDifferent = next;
differentCount++;
}
}
}
Теперь все мы нужно проанализировать наши цифры
int size = occurences.size();
if (benchmarkCount == size) return "YES"; // if all of the numbers are the same
if (benchmarkCount == size - 1) { // if we hit only single different
// either the diffent number is 1 or it is greater than our benchmark by value of 1
if (firstDifferent == 1 || firstDifferent - benchmark == 1) {
return "YES";
}
}
// same case with above
if (differentCount == size - 1) {
if (benchmark == 1 || benchmark - firstDifferent == 1) {
return "YES";
}
}
полное решение
static String isValid(String s) {
Map<Character, Integer> occurences = new HashMap<>();
s.chars().forEach(e-> occurences.put((char)e, occurences.getOrDefault((char)e, 0) + 1));
Iterator<Map.Entry<Character, Integer>> iterator = occurences
.entrySet()
.iterator();
int benchmark = iterator.next().getValue();
int benchmarkCount = 1;
int firstDifferent = -1;
int differentCount = 0;
while(iterator.hasNext()) {
int next = iterator.next().getValue();
if (next == benchmark) {
benchmarkCount++;
} else {
if (firstDifferent == -1 || firstDifferent == next) {
firstDifferent = next;
differentCount++;
}
}
}
int size = occurences.size();
if (benchmarkCount == size) return "YES";
if (benchmarkCount == size - 1) {
if (firstDifferent == 1 || firstDifferent - benchmark == 1) {
return "YES";
}
}
if (differentCount == size - 1) {
if (benchmark == 1 || benchmark - firstDifferent== 1) {
return "YES";
}
}
return "NO";
}