---
title: "🔤 Ultimate Guide to Solving the Lexicographically Smallest Equivalent String Problem on LeetCode (1061) | Easy-to-Follow C++, JavaScript, Python Solutions"
url: "https://binary.ph/2025/06/05/%f0%9f%94%a4-ultimate-guide-to-solving-the-lexicographically-smallest-equivalent-string-problem-on-leetcode-1061-easy-to-follow-c-javascript-python-solutions/"
description: "The ultimate guide to Solving Lexicographically Smallest Equivalent String Problem on LeetCode 1061 with easy C++, JavaScript, and Python solutions."
author: "BinaryPH"
published: "2025-06-05T03:01:38+00:00"
modified: "2025-06-05T03:01:38+00:00"
tags: ["Main"]
---

# 🔤 Ultimate Guide to Solving the Lexicographically Smallest Equivalent String Problem on LeetCode (1061) | Easy-to-Follow C++, JavaScript, Python Solutions

Welcome, fellow coding enthusiasts! 🚀 In this comprehensive guide, we’ll explore how to tackle the Lexicographically Smallest Equivalent String problem (LeetCode 1061) – an excellent exercise that combines string manipulation with graph theory concepts. Perfect for beginners and intermediate coders alike, we’ll walk through multiple solution approaches with detailed implementations in C++, JavaScript, and Python.

## 🔍 Understanding the Problem Statement

The challenge presents us with: 1. Two strings \`s1\` and \`s2\` of equal length 2. A third string called \`baseStr\`

Each character pair \`(s1[i], s2[i])\` establishes an equivalence relationship with these properties:

– \*\*Reflexive\*\*: Every character is equivalent to itself – \*\*Symmetric\*\*: If ‘a’ equals ‘b’, then ‘b’ equals ‘a’ – \*\*Transitive\*\*: If ‘a’ equals ‘b’ and ‘b’ equals ‘c’, then ‘a’ equals ‘c’

Your mission? Transform each character in \`baseStr\` to its lexicographically smallest equivalent character based on the relationships defined by \`s1\` and \`s2\`.

## 🧠 Problem-Solving Approach and Intuition

Visualizing this challenge as a graph problem provides our breakthrough insight:

1. \*\*Graph Representation\*\*: Each character becomes a node 2. \*\*Edges\*\*: Each \`(s1[i], s2[i])\` pair forms an undirected edge connecting nodes 3. \*\*Connected Components\*\*: Characters in the same equivalence class form connected components 4. \*\*Optimization Goal\*\*: For each component, we want to identify and use the smallest character

The \*\*Disjoint Set Union (DSU)\*\* data structure, also known as Union-Find, emerges as the perfect tool for this scenario with its efficient union and find operations.

## ⚡ Key DSU Operations for This Problem

1. \*\*Find Operation\*\*: Determines the root representative of a character (with path compression) 2. \*\*Union Operation\*\*: Connects two characters while maintaining the lexicographically smallest parent

## 👨‍💻 Solution Implementations

### C++ Implementation (With Optimized DSU) “\`cpp #include #include using namespace std;

class Solution { public: class DSU { vector parent; public: DSU(int n) { parent.resize(n); for (int i = 0; i < n; i++) parent[i] = i; }

int find(int x) { if (parent[x] != x) parent[x] = find(parent[x]); return parent[x]; }

void unionByLex(int x, int y) { int rootX = find(x); int rootY = find(y); if (rootX < rootY) parent[rootY] = rootX; else if (rootY < rootX) parent[rootX] = rootY; } };

string smallestEquivalentString(string s1, string s2, string baseStr) { DSU dsu(26); for (int i = 0; i i); }

find(x) { if (this.parent[x] !== x) { this.parent[x] = this.find(this.parent[x]); } return this.parent[x]; }

unionByLex(x, y) { const rootX = this.find(x); const rootY = this.find(y); if (rootX < rootY) this.parent[rootY] = rootX; else if (rootY < rootX) this.parent[rootX] = rootY; } }

function smallestEquivalentString(s1, s2, baseStr) { const dsu = new DSU(26); for (let i = 0; i < s1.length; i++) { dsu.unionByLex( s1.charCodeAt(i) – 97, s2.charCodeAt(i) – 97 ); }

let result = []; for (const c of baseStr) { const charCode = dsu.find(c.charCodeAt(0) – 97); result.push(String.fromCharCode(charCode + 97)); }

return result.join(''); } “\`

### Python Implementation “\`python class DSU: def \_\_init\_\_(self, n): self.parent = list(range(n))

def find(self, x): if self.parent[x] != x: self.parent[x] = self.find(self.parent[x]) return self.parent[x]

def union(self, x, y): rootX = self.find(x) rootY = self.find(y) if rootX < rootY: self.parent[rootY] = rootX elif rootY str: dsu = DSU(26) for a, b in zip(s1, s2): dsu.union(ord(a) – ord(‘a’), ord(b) – ord(‘a’))

result = [] for c in baseStr: smallest\_char = chr(dsu.find(ord(c) – ord(‘a’)) + ord(‘a’)) result.append(smallest\_char)

return ”.join(result) “\`

## 💡 Pro Tips for Mastering Similar Problems

1. Always analyze the problem for underlying graph structures 2. Consider equivalence relations carefully—they often suggest union-find solutions 3. Practice implementing DSU with various optimizations (path compression, union by rank/size) 4. For lexicographical problems, maintain ordering during union operations 5. Don’t forget to convert between character representations and numerical indices

## 🔗 Additional Resources for Problem Solving

Looking to enhance your problem-solving skills further? Consider exploring: – More graph and DSU problems on LeetCode – Algorithm visualization tools to better understand union-find – Competitive programming resources that cover data structures in depth – Pair programming sessions to discuss different approaches to these problems

Happy coding! Remember, the journey of a thousand algorithms begins with a single for-loop. 🏆