A list of lowercase words words is claimed to be sorted according to some unknown alphabet (a permutation of the letters that appear). Return a string containing every letter that appears in words exactly once, in an order consistent with the sorting. If several alphabets are consistent, return any of them. If none is (the list cannot be sorted under any alphabet), return "".
Recall that under any alphabet, a word comes before any longer word that starts with it.
Examples
Input: words = ["wrt", "wrf", "er", "ett", "rftt"]
Output: "wertf"
Input: words = ["z", "x"]
Output: "zx"
Input: words = ["z", "x", "z"]
Output: ""
Input: words = ["abc", "ab"]
Output: ""
Explanation: "abc" can never come before its own prefix "ab".
Your answer is checked for consistency with the constraints, so any valid alphabet passes.
Constraints
1 <= len(words) <= 500,1 <= len(words[i]) <= 100, lowercase letters only- Target: O(total characters) time.
Goals
- Derive ordering constraints from adjacent words in a sorted list
- Recognise the invalid prefix case and cycles as 'no valid alphabet'
- Output any ordering consistent with all constraints