Ring of Flippable Words

Medium

You are given a list of words pieces. They are written around a circle in the given order, so the last word is followed by the first one again. Before that, each word may be kept as is or reversed, independently of the others. Then the ring is cut at one spot and read clockwise from the cut, giving an ordinary string of the same length. Return the lexicographically largest string you can get this way.

Example 1

pieces=['ram', 'top'] → 'trampo'

Keep ram as is and flip top into pot. Cut the ring rampot right before its last letter t and read on around the circle: trampo.

Example 2

pieces=['bca'] → 'cba'

A single word forms the ring on its own. Flip it to acb and cut before c to get cba.

Example 3

pieces=['ab', 'zc', 'b'] → 'zcbba'

Constraints

1 ≤ len(pieces) ≤ 1000
1 ≤ len(pieces[i]) ≤ 1000
The total length of all words is at most 1000
Words consist of lowercase English letters

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Greedy Array String

Similar problems

Biggest Number From Pieces Medium Smallest Up-Down Sequence Medium Drop Columns to Keep Rows Sorted Medium Round Prices to a Total Medium Bead String Without Twins Medium

Input

pieces=['ram', 'top']

Expected

'trampo'

Run checks the first 3 tests in your browser. Submit checks all 112 tests on the server, hidden ones included.