1001HardArrayHash TableStringTrieHash Function

Pairs of Labels That Read the Same Both Ways

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

Labels are given as labels, each a string of lowercase letters. A label may be empty, and two labels may read alike while sitting at different positions in the list.

Return every ordered pair of positions [i, j] with i and j different, such that the label at i written straight before the label at j, with nothing between them, reads the same backwards as forwards.

List the pairs in increasing order, comparing the first position and, where those match, the second.

Examples

Example 1

Input: labels = ["ab", "ba"]
Output: [[0, 1], [1, 0]]

Either way round the two labels join into a four-letter string that reads the same backwards, so both orderings count.

Example 2

Input: labels = ["race", "ecar", "car", "rac"]
Output: [[0, 1], [0, 2], [1, 0], [2, 3], [3, 1], [3, 2]]

Six joins work. Position 0 goes before positions 1 and 2, position 1 goes before position 0, position 2 goes before position 3, and position 3 goes before positions 1 and 2. Position 0 before position 3 fails: that join runs to seven letters and its two ends do not answer each other.

Example 3

Input: labels = ["ab", "cd"]
Output: []

Neither ordering of the two labels reads the same backwards, so nothing is reported.

Constraints

1 <= labels.length <= 5000
0 <= labels[i].length <= 300
Every label is made of lowercase English letters.

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def palindrome_pairs(labels: list[str]) -> list[list[int]]:

Java

public List<List<Integer>> palindromePairs(String[] labels)

The intended approach

Time O(n * L^2 + P log P) for n labels of length at most L and P pairs found.Space O(n * L + P) for the table and the pairs.

Put one label straight before another and read the join from both ends inwards. The shorter of the two labels has to answer the far end of the longer one letter for letter. Say the front label is at least as long as the back one. The join's closing stretch is the back label itself, and the stretch of matching length at the very start is the front label's opening. Those two have to be each other reversed. Once they have answered each other, what is left in the middle is the rest of the front label, which then has to read the same both ways on its own. When the back label is the longer, the mirror of that holds: the front label has to be the reverse of the back label's closing stretch of matching length, and the back label's remaining opening has to read the same both ways. So build a table from label to the positions holding it, then take each label and cut it at every place. Where the cut's back piece reads the same both ways, any label matching the front piece reversed can go behind this one. Where the cut's front piece reads the same both ways, any label matching the back piece reversed can go in front of it, and that side is taken only for cuts past the very start, since equal lengths are already covered by the other side. A position never pairs with itself. Sorting the pairs at the end puts them in the order asked for. Cutting costs the label's length squared at worst, which is what a table lookup buys over comparing every pair of labels outright.

Pythonentry point: palindrome_pairs

def palindrome_pairs(labels):
    where = {}
    for idx, text in enumerate(labels):
        where.setdefault(text, []).append(idx)
    def mirror(piece):
        return piece == piece[::-1]
    found = set()
    for w, text in enumerate(labels):
        n = len(text)
        for cut in range(n + 1):
            head = text[:cut]
            tail = text[cut:]
            if mirror(tail):
                for j in where.get(head[::-1], ()):
                    if j != w:
                        found.add((w, j))
            if cut > 0 and mirror(head):
                for i in where.get(tail[::-1], ()):
                    if i != w:
                        found.add((i, w))
    return [[a, b] for a, b in sorted(found)]

The obvious version

Take every ordered pair of positions, join the two labels and check the joined string against itself reversed, keeping the pairs that match. Walking the positions in order already yields them sorted. Costs every pair times the joined length rather than a table of labels.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_palindrome_pairs(labels):
    out = []
    n = len(labels)
    for i in range(n):
        for j in range(n):
            if i == j:
                continue
            joined = labels[i] + labels[j]
            if joined == joined[::-1]:
                out.append([i, j])
    return out

How this problem was checked

Reference solution executed against 16 test cases — 16 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in