Попытка найти самый длинный палиндром для этого ввода

Question

Учитывая строку, которая состоит из строчных или прописных букв, найдите длину самых длинных палиндромов, которые можно построить с помощью этих букв.

Это чувствительно к регистру, например, "Aa" здесь не считается палиндромом.

Примечание:

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

Пример:

Ввод: "abccccdd"

Выход: 7

Пояснение:

Один из самых длинных палиндромов, который может быть построен, это "dccaccd", длина которого равна 7.

Мой код работает для простых вводов, таких как "abccccdd" и "banana", но не работает для "civilwartestingwhetherthatnaptionoranynartionsoconceivedandsodedicatedcanlongendureWeareqmetonagreatbattlefiemldoftzhatwarWehavecometodedicpateaportionofthatfieldasafinalrestingplaceforthosewhoheregavetheirlivesthatthatnationmightliveItisaltogetherfangandproperthatweshoulddothisButinalargersensewecannotdedicatewecannotconsecratewecannothallowthisgroundThebravelmenlivinganddeadwhostruggledherehaveconsecrateditfaraboveourpoorponwertoaddordetractTgheworldadswfilllittlenotlenorlongrememberwhatwesayherebutitcanneverforgetwhattheydidhereItisforusthelivingrathertobededicatedheretotheulnfinishedworkwhichtheywhofoughtherehavethusfarsonoblyadvancedItisratherforustobeherededicatedtothegreattdafskremainingbeforeusthatfromthesehonoreddeadwetakeincreaseddevotiontothatcauseforwhichtheygavethelastpfullmeasureofdevotionthatweherehighlyresolvethatthesedeadshallnothavediedinvainthatthisnationunsderGodshallhaveanewbirthoffreedomandthatgovernmentofthepeoplebythepeopleforthepeopleshallnotperishfromtheearth". Я не уверен, как отладить это.

class Solution {
    public int longestPalindrome(String s) {
        Map<Character, Integer> map = new HashMap<>();
        char[] carr = s.toCharArray();
        Arrays.sort(carr);
        int leftInd = 0;
        int rightInd = 0;
        for(int i=0; i<carr.length; i++){
            if(map.containsKey(carr[i]))
                continue;
            else
                map.put(carr[i], 1);
        }
        for(int i=0; i<carr.length-1; i++){
            for(int j=i+1; j<carr.length; j++){
                if(carr[i]==carr[j]){
                    if(map.get(carr[i])==null)
                        continue;
                    carr[j] = Character.MIN_VALUE;
                    int count = map.get(carr[i]);
                    map.put(carr[i], count + 1);
                }
            }
        }
        int ans = 0;
        int[] oddValArr = new int[map.size()];
        int oddInd = 0;
        for (Map.Entry<Character, Integer> entry : map.entrySet()) {
            Character key = entry.getKey();
            Integer value = entry.getValue();
            if(value % 2 == 0){
                ans += value;
            }
            else{
                oddValArr[oddInd] = value;
                oddInd++;
            }
        }
        int biggestOddNum = 0;
        for(int i=0; i<oddValArr.length; i++){
            if(oddValArr[i] > biggestOddNum)
                biggestOddNum = oddValArr[i];
        }
        return ans + biggestOddNum;
     }
}

Выход 655

Ожидаемая 983

Answer 1

Ваша ошибка здесь в том, что вы используете только самую большую нечетную группу из вашей oddValArr. Например, если ввод «aaabbb», самый большой палиндром - «abbba», поэтому группа a имела длину 3, которая является нечетным числом, и мы использовали 3 - 1 = 2 букв этого числа.

Кроме того, эти вложенные циклы for можно заменить одним for, используя Map:

public int longestPalindrome(String s) {
    Map<Character, Integer> map = new HashMap<>();  // letter groups
    for(int i=0; i<s.length(); i++){
        char c = s.charAt(i));
        if(map.containsKey(c))
            map.put(c, map.get(i) + 1);
        else
            map.put(c, 1);
    }

    boolean containsOddGroups = false;
    int ans = 0;
    for(int count : map.values()){
        if(count % 2 == 0)  // even group
            ans += count;
        else{  // odd group
            containsOddGroups = true;
            ans += count - 1;
        }
    }
    if(!containOddGroups)
        return ans;
    else
        return ans + 1;  // we can place one letter in the center of palindrome
}

Answer 2

Вы почти на месте, но немного усложнили.Мое решение - почти только удалить код из вашего решения:

public static int longestPalindrome(String s) {
    Map<Character, Integer> map = new HashMap<>();
    char[] carr = s.toCharArray();
    for (int i = 0; i < carr.length; i++) {
        if (map.containsKey(carr[i]))
            map.put(carr[i], map.get(carr[i]) + 1);
        else
            map.put(carr[i], 1);
    }

    int ans = 0;
    int odd = 0;
    for (Integer value : map.values()) {
        if (value % 2 == 0) {
            ans += value;
        } else {
            ans += value - 1;
            odd = 1;
        }
    }
    return ans + odd;
}

Объяснение:

• второй цикл был удален вместе с сортировкой - он был объединен с первымпетля.В сортировке вообще не было необходимости.
• , тогда вы повторяете счетчик того, как часто символ появляется
  • , если даже вы увеличиваете ans, как и раньше
  • если он нечетный, вы можете использовать count - 1 его символов для палиндрома четной длины
• если вы нашли хотя бы одно нечетное вхождение, вы можете поместить этот нечетный символ в центрпалиндром и увеличьте его длину на один