Show problems as
Classic problem #409EasyHash TableStringGreedy

Longest Palindrome

Real-world version: Longest Lintel Row of Carved Tiles
Tracked in this browser only
Read Longest Palindrome on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A mason keeps carved letter tiles loose in a crate. crate gives the carving on each tile, in the order the tiles come out of the crate. Carvings are cut with either an upper-case punch or a lower-case punch, and the two are different tiles: a tile carved S will not pass for a tile carved s.

The mason lays some of the tiles in one row along a lintel. The tiles may be laid in any order, any number of them may be left in the crate, and no tile can be used twice. The row must read the same scanned left to right as scanned right to left.

Return the largest number of tiles such a row can contain.

Examples

Example 1

Input
crate = "ledgerledger"
Output
12

All twelve tiles go into the row, for example laid as `ledgerregdel`, which reads the same from either end.

Example 2

Input
crate = "Zz"
Output
1

The two tiles carry different carvings, so the row holds a single tile, and one tile reads the same either way.

Example 3

Input
crate = "ppqr"
Output
3

A row of three such as `pqp` uses both `p` tiles and one of the remaining two; the last tile stays in the crate.

Example 4

Input
crate = "granitegranit"
Output
13

Thirteen of the tiles form a row, for instance `granitetinarg`.

Constraints

  • 1 <= crate.length <= 2000
  • crate consists of lower-case and/or upper-case English letters only.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def longest_band(crate: str) -> int:
Java
public int longestBand(String crate)

More on the same topics