Build equivalence classes among letters and replace each character with the smallest possible equivalent letter.
Smallest Equivalent String
gfgYou are given two strings of equal length, s1 and s2, where s1[i] is equivalent to s2[i] for every index i. This equivalence is transitive and symmetric, so if a is equivalent to b and b is equivalent to c, then all three letters belong to the same group.
You are also given a string baseStr. For each character in baseStr, replace it with the lexicographically smallest character in its equivalence group. Return the resulting string.
The equivalence relations apply only to lowercase English letters a to z.
Your task is to compute the smallest possible string after applying all valid character replacements.
Input Format
s1: a lowercase strings2: a lowercase string of the same length ass1baseStr: a lowercase string to transform
Output Format
- Return a string of the same length as
baseStr, where each character is replaced by the smallest equivalent letter in its group.
Constraints
1 <= s1.length == s2.length <= 10001 <= baseStr.length <= 1000- All characters are lowercase English letters.
Example 1
Input
s1 = "parker", s2 = "morris", baseStr = "parser"
Output
"makkek"
Explanation
The relations connect letters into groups such as {p,m}, {a,o}, {r,r,s?}, etc. Replacing each character in parser with the smallest equivalent letter yields makkek.
Example 2
Input
s1 = "hello", s2 = "world", baseStr = "hold"
Output
"hdld"
Explanation
Letters are grouped by the equivalence relations from s1 and s2. Each character in hold is replaced by the smallest letter in its connected group.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.