CodingGyan

Longest Palindrome from Letters

easy Strings

Problem

A word is given (letters are case-sensitive: a and A are different). You may pick any of its letters, and arrange them in any order. Print the length of the longest palindrome that you can build.

Constraints

  • 1 <= length <= 10^5

Examples

Input

abccccdd

Output

7

Solutions

Best approachTime O(n)Space O(1)

Equal letters in pairs can be placed on the two sides. At most one letter can stay in the middle. So the answer is the number of letters in pairs, plus 1 if any letter is left over.

Same code works in Java810172125Basic features only, so nothing changes between versions.
/*
 * Problem : Longest palindrome.
 * Input   : One word.
 * Output  : The length.
 * Approach: Count the pairs
 * Time    : O(n)
 * Space   : O(1)
 * Java    : 8 or newer.
 */
import java.util.Scanner;

public class Main {
    // This method solves the task. It receives the input and returns the answer.
    static long solve(String s) {
        // Step 1: Count each letter. A pair of equal letters can go on both sides of the palindrome.
        int[] counts = new int[128];
        for (int i = 0; i < s.length(); i++) {
            counts[s.charAt(i)]++;
        }
        int length = 0;
        boolean hasOdd = false;
        for (int count : counts) {
            length += count / 2 * 2;
            if (count % 2 == 1) {
                hasOdd = true;
            }
        }
        // Step 2: One single letter can stay in the middle.
        return hasOdd ? length + 1 : length;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.hasNextLine() ? scanner.nextLine() : "";
        System.out.println(solve(s));
    }
}
Hints (1)
  1. What goes in the middle?

Try these next