Katkat
Back

Infer the Smallest Valid Character Order from Sorted Password Hints

RogoMachine Learning Engineer · Onsite
MediumMachine Learning EngineerOnsiteCoding & Algorithms

Last updated

This problem tests your ability to model dependency constraints using a Directed Acyclic Graph (DAG) and apply Kahn's algorithm or DFS-based topological sorting to resolve ordering dependencies.

Problem Statement

You are given a list of password hints, which are strings already sorted in lexicographical order based on an unknown character alphabet. Your task is to reconstruct a valid order of these characters.

If there are multiple valid orders, return the one that is lexicographically smallest. If the provided list is inconsistent (i.e., a circular dependency or an impossible prefix order), return an empty string.

Function Signature

def find_smallest_alphabet(words: List[str]) -> str:

Constraints

  • 1 <= words.length <= 100
  • 1 <= words[i].length <= 100
  • The alphabet contains only lowercase English letters.

Examples

Example 1: Input: ["zy", "zx"] Output: "yxz" Explanation: 'y' must come before 'x'. All characters present ('z', 'y', 'x') must be included.

Example 2: Input: ["wrt", "wrf", "er", "ett", "rftt"] Output: "wertf"

Edge Cases:

  • Empty input or single-word inputs should return all unique characters in the input sorted alphabetically.
  • If a word is a prefix of a previous word but appears later in the list, it is an invalid constraint (e.g., ["abc", "ab"]).

Hints

Hint 1

Identify edges by comparing adjacent words: find the first character where they differ to establish a dependency.

Hint 2

Model the dependencies as a directed graph where an edge from u to v means u must appear before v.

Hint 3

Use a min-priority queue with Kahn's algorithm to ensure that when multiple characters are available to be placed next, you always pick the smallest one lexicographically.

Follow-up questions

  • How would you modify your algorithm if the alphabet size was unknown or potentially included symbols beyond lowercase letters?
  • What is the time complexity of your solution in terms of total characters in the input and the size of the alphabet?
  • How would you handle the situation where the input is missing characters that were part of the intended alphabet?