bugl
bugl
HomeLearnPatternsPathsSearchPremium
HomeLearnPatternsPaths
MediumGraphsLC 1061

Lexicographically Smallest Equivalent String

You are given two strings of the same length s1 and s2 and a string baseStr. We say s1[i] and s2[i] are equivalent characters. For example, if s1 = "abc " and s2 = "cde ", then we have 'a' == 'c', 'b' == 'd', and 'c' == 'e'. Equivalent characters follow the usual rules of any equivalence relation: Reflexivity: 'a' == 'a'. Symmetry: 'a' == 'b' implies 'b' == 'a'. Transitivity: 'a' == 'b' and 'b' == 'c' implies 'a' == 'c'. For example, given the equivalency information from s1 = "abc " and s2 = "cde ", "acd " and "aab " are equivalent strings of baseStr = "eed ", and "aab " is the lexicographically smallest equivalent string of baseStr.

Hints
  • 1.Think about which data structure fits best
  • 2.Consider the time complexity of your approach
  • 3.Look for patterns in the constraints
LeetCode