FastPrepReturn the Last Seen Anagram in a Word Stream
Problem · Array

Return the Last Seen Anagram in a Word Stream

Learn this problem
● MediumAmazon logoAmazonNEW GRADONSITE INTERVIEW
See Amazon hiring insights

Problem statement

Process the lowercase words in words from left to right. For each arriving word:

  • If an earlier word is an anagram of it, append the most recently seen such word to the answer.
  • Otherwise, append the arriving word itself.

After producing the output for an arrival, remember that word as the newest word for its anagram group. Return one output per input word.

Function

lastSeenAnagrams(words: String[]) → String[]

Examples

Example 1

words = ["listen","cat","silent","act","enlist"]return = ["listen","cat","listen","cat","silent"]

Silent returns listen, act returns cat, and enlist returns silent because it is the newest word in that group.

Example 2

words = ["red","blue","green"]return = ["red","blue","green"]

Every arriving word starts a new signature group.

Example 3

words = ["a","a","b","a"]return = ["a","a","b","a"]

An exact earlier copy also counts as an anagram and becomes the most recent match.

Constraints

  • 1 <= words.length <= 100000.
  • 1 <= words[i].length <= 40.
  • Every word contains only lowercase English letters.
  • The total number of characters is at most 200000.

More Amazon problems

drafts saved locally
public String[] lastSeenAnagrams(String[] words) {
  // write your code here
}
words["listen","cat","silent","act","enlist"]
expected["listen", "cat", "listen", "cat", "silent"]
checking account