Letters Into Trays

Medium

A sorting machine drops letters into trays. The trays stand in a row from left to right and are labelled with the letters of trays (no letter repeats there). The letters of letters enter the machine one by one, from left to right. Each letter falls into the tray with its own label. If there is no such tray, the letter falls into the very first (leftmost) tray. Within a tray, letters stay in the order they arrived. Once every letter is sorted, the machine empties the trays from left to right. Return the resulting string.

Example 1

trays="tea", letters="eatbet" → 'tbteea'

The trays from left to right are t, e, a. There is no tray for b, so it falls into the first tray together with the ts, in order of arrival: t, b, t. Then come e, e and a, giving "tbteea".

Example 2

trays="kq", letters="qkq" → 'kqq'

First the k tray with one letter, then the q tray with two.

Example 3

trays="z", letters="hello" → 'hello'

Constraints

1 ≤ len(trays) ≤ 26
1 ≤ len(letters) ≤ 200
Both strings consist of lowercase English letters
No letter repeats in trays

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Hash Table String Sorting

Similar problems

Anagram Buckets Medium Characters Grouped by Count Medium A Subsequence of One Word Only Medium Most Searched Words Medium Word Grown Letter by Letter Medium

Input

trays="tea", letters="eatbet"

Expected

'tbteea'

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