Java | LeetCode
Задача: 409. Longest Palindrome
Сложность: easy
Если задана строка s, состоящая из строчных или прописных букв, верните длину самого длинного палиндрома, который можно построить из этих букв. Буквы чувствительны к регистру, например, "Aa" не считается палиндромом.
Пример:
Input: s = "abccccdd"
Output: 7
👨💻 Алгоритм:
1⃣Создайте словарь для подсчета количества каждого символа в строке.
2⃣Пройдитесь по словарю и добавьте четное количество каждого символа к длине палиндрома. Если встречается нечетное количество символа, добавьте (count - 1) к длине палиндрома.
3⃣Если есть хотя бы один символ с нечетным количеством, добавьте 1 к длине палиндрома для центрального символа.
😎 Решение:
import java.util.HashMap;
import java.util.Map;
public class Solution {
public int longestPalindrome(String s) {
Map<Character, Integer> charCount = new HashMap<>();
for (char c : s.toCharArray()) {
charCount.put(c, charCount.getOrDefault(c, 0) + 1);
}
int length = 0;
boolean oddFound = false;
for (int count : charCount.values()) {
if (count % 2 == 0) {
length += count;
} else {
length += count - 1;
oddFound = true;
}
}
return oddFound ? length + 1 : length;
}
}
Ставь 👍 и забирай 📚 Базу знаний
1 · 367 ·