In a word game, lowercase letter tiles are arranged in a row. You want to take one continuous group of tiles and use its letters to form a given word.

Find the shortest continuous group containing enough letters to form the word after rearranging them.

Class

WordTileFinder

Method

findShortestTileGroup

String findShortestTileGroup(String tileRow, String targetWord)

Parameters

• tileRow: The letters on the tiles from left to right.
• targetWord: The word that must be formed.

Returns

Return the shortest continuous part of tileRow containing all letters required to form targetWord.

Return an empty string if no such group exists. If multiple shortest groups exist, return the one starting at the lowest index.

Rules

• The selected tiles must be consecutive in tileRow.
• The selected letters may be rearranged in any order.
• Every occurrence of a letter in targetWord must be available in the selected group.
• The selected group may contain additional unused letters.

Constraints

• 1 ≤ tileRow.length() ≤ 100,000
• 1 ≤ targetWord.length() ≤ 100,000
• tileRow and targetWord contain only lowercase English letters.

Examples

Example 1

findShortestTileGroup( tileRow = "xbroawdc", targetWord = "word")

Output: "roawd"

The letters in "roawd" include 'w', 'o', 'r', and 'd'. They can be rearranged to form "word".

Example 2

findShortestTileGroup( tileRow = "aoboklobo", targetWord = "book")

Output: "obok"

The group contains one 'b', two 'o' letters, and one 'k'.

Example 3

findShortestTileGroup( tileRow = "garden", targetWord = "green")

Output: ""

The word requires two 'e' letters, but the tile row contains only one.

Example 4

findShortestTileGroup( tileRow = "cabxxabc", targetWord = "abc")

Output: "cab"

Both "cab" and "abc" are shortest valid groups. Since "cab" starts first, it is returned.