Runtime - O(n) 💯 || Memory - O(1) ⭐️ || Easy Solution ✅ || Fully Explained ✅
Approach\n\nApproach: Union-Find (Disjoint Set Union)\n\nStep 1: Initialize Parent Array\n- We\'ll create an array called parent of size 26 (one for each lowerc
# Approach\n\n**Approach: Union-Find (Disjoint Set Union)**\n\n**Step 1: Initialize Parent Array**\n- We\'ll create an array called `parent` of size 26 (one for each lowercase English letter).\n- We\'ll initialize each character to be its own parent initially.\n\n**Step 2: Establish Equivalency Relationships**\n- For each character at the same position in `s1` and `s2`, we\'ll find their respective parents using the `findParent` function.\n- If the parent of `s1[i]` is lexicographically smaller than the parent of `s2[i]`, we\'ll set the parent of `s2[i]` to be the parent of `s1[i]`. Otherwise, we\'ll set the parent of `s1[i]` to be the parent of `s2[i]`.\n- This step groups equivalent characters under the same parent.\n\n**Step 3: Transform Base String**\n- For each character in the `baseStr`, we\'ll find its parent using the `findParent` function and append the corresponding transformed character to a `result` StringBuilder.\n- This transformation ensures that characters in the `baseStr` are changed to their lexicographically smallest equivalents based on the established equivalency relationships.\n\n**Step 4: Return Result**\n- Convert the `result` StringBuilder to a String and return it as the final lexicographically smallest equivalent string.\n\n**Logic:**\n- We\'re given two strings `s1` and `s2` that define equivalency relationships between characters. Using this information, we create groups of equivalent characters using Union-Find.\n- By associating characters with their parent in the `parent` array, we\'re able to efficiently find the smallest equivalent character in each group.\n- Finally, we transform the characters in the `baseStr` using the established relationships, ensuring that we get the lexicographically smallest equivalent string.\n\n# Complexity\n- Time complexity: $$O(n)$$\n\n- Space complexity: $$O(1)$$\n\n# Code\n```\nclass Solution {\n    int[] parent = new int[26];\n\n    public String smallestEquivalentString(String s1, String s2, String baseStr) {\n        for (int i = 0; i < 26; i++) {\n            parent[i] = i;\n        }\n\n        for (int i = 0; i < s1.length(); i++) {\n            int parentS1 = findParent(s1.charAt(i) - \'a\');\n            int parentS2 = findParent(s2.charAt(i) - \'a\');\n            if (parentS1 < parentS2) {\n                parent[parentS2] = parentS1;\n            } else {\n                parent[parentS1] = parentS2;\n            }\n        }\n\n        StringBuilder result = new StringBuilder();\n        for (char c : baseStr.toCharArray()) {\n            int parentC = findParent(c - \'a\');\n            result.append((char) (parentC + \'a\'));\n        }\n\n        return result.toString();\n    }\n\n    private int findParent(int c) {\n        if (parent[c] == c) return c;\n        return parent[c] = findParent(parent[c]);\n    }\n}\n```
['String', 'Union Find', 'Java', 'C#']