Получить все возможные палиндромы из заданной строки

Question

Подстрока - это непрерывный диапазон символов в строке.

Теперь мне нужно выяснить, сколько подстрок, которые можно переставить, может образовать палиндром.

Например: Для ввода - aabb

a
aa
aab (because after re-arranging it becomes aba)
aabb (because after re-arranging it becomes abba)
a
abb (because after re-arranging it becomes bab)
b
bb
b

So we have 9 substring palindromes.

Вот код, который я попробовал:

public static int getPalindromeCount(String str) {
    // all single characters are treated as palindrome
    int count = str.length();

    // Get all sub strings
    List<String> subs = new ArrayList<>();
    subString(str, subs);

    for (String sub : subs) {
        String rev = new StringBuilder(sub).reverse().toString();

        if (rev.equals(sub)) {
            System.out.println(sub);
            count++;
        } else {
            boolean valid = isPalindrome(sub);
            System.out.println(sub + " : " + valid);
            if (valid) {
                count++;
            }
        }
    }
    return count;
}

// Check if substring can form a Palindrome
private static boolean isPalindrome(String input) {
    Set<Character> oddChars = new HashSet<>();

    for (char c : input.toCharArray()) {
        if (!oddChars.add(c)) {
            oddChars.remove(c);
        }
    }
    return oddChars.size() <= 1;
}

// Get all substrings
private static void subString(String input, List<String> list) {
    for (int i = 0; i < input.length(); i++) {
        for (int j = i + 2; j <= input.length(); j++) {
            list.add(input.substring(i, j));
        }
    }
}

Метод isPalindrome часть логики, которую я взял из этого поста Проверьте, может ли перестановка строки стать палиндромом

Этот код работает нормально, но не работает с ошибками тайм-аута.

Я не уверен, чтовходы, для которых это не удается, поскольку они скрыты в моем вызове хакерранка.

Редактировать:

Я изменил свой метод getPalidromeCount, чтобы проверить, сколько нечетныхколичество букв, которые вводятся для определения числа палиндромов.

Это основано на комментариях к этому сообщению:

Подсказка: палиндром состоит из всех букв четного числа или всех буквчетного счета с одной буквой нечетного счета (средний символ).Теперь вы можете легко подсчитать возможные палиндромы.- vivek_23

public static int getPalindromeCount(String str) {
    List<Integer> list = new ArrayList<>(strToEvaluate.size());
    for (String str : strToEvaluate) {
        int count = str.length();

        List<String> subs = new ArrayList<>();
        subString(str, subs);
        for (String sub : subs) {
            Map<Character, Integer> map = new HashMap<>();
            for (int i = 0; i < sub.length(); i++) {
                char c = sub.charAt(i);
                map.put(c, map.getOrDefault(c, 0) + 1);
            }
            int odds = 0;
            for (char key : map.keySet()) {
                if (map.get(key) % 2 != 0) {
                    odds++;
                    if (odds > 1) {
                        break;
                    }
                }
            }
            if (odds <= 1) {
                System.out.println(sub);
                count++;
            }

            list.add(count);
        }
    }
    return list;
}

Но все же я вижу ошибки тайм-аута.Я не использую метод isPalindrome в этой логике.

Answer 1

Существует n(n+1)/2 возможных подстрок, и для каждой подстроки вы проверяете, можно ли переставить ее так, чтобы она формировала палиндром в O(k), где k - длина данной подстроки, давайте подумаем, нужно ли разбирать каждую подстроку отдельно.

Совет:

Допустим, у вас есть подстрока из индекса p до k, что вы можете сказать о подстроке из индекса p до k + 1. Действительно ли необходимо анализировать эту расширенную подстроку отдельно?

Answer 2

• Я предполагаю, что строка состоит из строчных букв. Если нет, вы можете увеличить размер хеша в массиве ниже, чтобы приспособить значения ASCII или лучше использовать карту для символов UTF-8.
• Вместо того, чтобы собирать все подстроки и затем индивидуально проверять каждую (что заняло бы O (n ² ) пробел, вы могли бы просто перебирать их по пути, увеличивать текущее количество символов и проверять палиндроменесс) как показано ниже.

Код:

 class Solution{
  public static long getPalindromeCount(String s) {
    long cnt = 0,len = s.length();    
    for(int i=0;i<len;++i){
       int[] hash = new int[26];
       cnt++; // since 1 character is palindrome anyway
       for(int j=i+1;j<len;++j){
          hash[s.charAt(j)-'a']++;
          if(palindromePossible(hash)) cnt++; 
       }
    }
    return cnt;
  }

  private static boolean palindromePossible(int[] hash){
    int odd_cnt = 0;
    for(int i=0;i<hash.length;++i){
      if(hash[i] % 2 != 0) odd_cnt++;
    }
    return odd_cnt < 2;
  }

  public static void main(String[] args){
    System.out.println(getPalindromeCount("aabb"));
  }
}