Являются ли строки перестановками друг друга

47. Проверить являются ли строки перестановками друг друга

Условие задачи:
Необходимо реализовать метод arePermutations(String a, String b), который проверяет, состоят ли строки из одинаковых символов с одинаковым количеством вхождений.

Порядок символов может отличаться.

Код:

System.out.println(arePermutations("abc", "bca"));   // true
System.out.println(arePermutations("aab", "aba"));   // true
System.out.println(arePermutations("abc", "abcc"));  // false
System.out.println(arePermutations("", ""));         // true
System.out.println(arePermutations(null, "abc"));    // false

Спойлеры к решению

Подсказки

💡 Если одна из строк равна null, верни false.
💡 Строки разной длины не могут быть перестановками.
💡 Простой вариант — отсортировать символы и сравнить массивы.
💡 Более эффективный вариант — посчитать частоты символов.

Решение

Вариант через сортировку:

static boolean arePermutations(String a, String b) {
    if (a == null || b == null) {
        return false;
    }

    if (a.length() != b.length()) {
        return false;
    }

    char[] first = a.toCharArray();
    char[] second = b.toCharArray();

    Arrays.sort(first);
    Arrays.sort(second);

    return Arrays.equals(first, second);
}

Временная сложность — O(n log n), дополнительная память — O(n).

Вариант через подсчёт частот:

static boolean arePermutationsLinear(String a, String b) {
    if (a == null || b == null) {
        return false;
    }

    if (a.length() != b.length()) {
        return false;
    }

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

    for (char symbol : a.toCharArray()) {
        frequencies.merge(symbol, 1, Integer::sum);
    }

    for (char symbol : b.toCharArray()) {
        Integer count = frequencies.get(symbol);

        if (count == null) {
            return false;
        }

        if (count == 1) {
            frequencies.remove(symbol);
        } else {
            frequencies.put(symbol, count - 1);
        }
    }

    return frequencies.isEmpty();
}

Временная сложность — O(n), дополнительная память — O(k), где k — количество уникальных символов.

Пустые строки считаются перестановками друг друга, поскольку обе содержат одинаковый набор символов.