Lexicographically Smallest Equivalent String

Lexicographically Smallest Equivalent String - Problem

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.

Return the lexicographically smallest equivalent string of baseStr by using the equivalency information from s1 and s2.

Input & Output

Example 1 — Basic Case

$ Input: s1 = "abc", s2 = "cde", baseStr = "eed"

› Output: "aab"

💡 Note: Equivalencies: 'a'=='c', 'b'=='d', 'c'=='e'. By transitivity: 'a'=='c'=='e', so group {a,c,e} has root 'a'. Group {b,d} has root 'b'. So "eed" becomes "aab".

Example 2 — Self Equivalency

$ Input: s1 = "leetcode", s2 = "programs", baseStr = "sourcecode"

› Output: "aauaaaaada"

💡 Note: Multiple character equivalencies create several groups. Each character in baseStr is replaced by its group's lexicographically smallest character.

Example 3 — No Changes

$ Input: s1 = "a", s2 = "b", baseStr = "xyz"

› Output: "xyz"

💡 Note: Only 'a' and 'b' are equivalent. Characters 'x', 'y', 'z' in baseStr remain unchanged since they have no equivalencies.

Constraints

1 ≤ s1.length, s2.length, baseStr.length ≤ 1000
s1.length == s2.length
s1, s2, and baseStr consist of lowercase English letters.

Visualization

Tap to expand

Understanding the Visualization

Input

s1="abc", s2="cde", baseStr="eed"

Group Characters

Form equivalency groups: {a,c,e} and {b,d}

Transform

Replace each character with group's smallest: "aab"

Key Takeaway

🎯 Key Insight: Use Union-Find to efficiently group equivalent characters and find the lexicographically smallest representative for each group

Asked in

G Google 25 a Amazon 18 f Facebook 15

The key insight is to use Union-Find to efficiently group equivalent characters. Each group's representative is the lexicographically smallest character. Best approach uses Union-Find with path compression. Time: O(n × α(26)), Space: O(26).

Common Approaches

Approach	Time	Space	Notes
✓ Union-Find (Optimal)	O(n × α(26))	O(26)	Use Union-Find to efficiently group equivalent characters and find representatives
Brute Force DFS	O(n × 26²)	O(26²)	For each character, explore all possible equivalent characters using DFS

Union-Find (Optimal) — Algorithm Steps

Initialize Union-Find for all 26 lowercase letters
Union characters from s1 and s2 pairs
For each character in baseStr, find its root representative

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Each character is its own parent initially

Union Operations

Connect equivalent characters with smaller root

Find Representatives

Each character maps to its group's smallest character

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int parent[26];

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

void unionSet(int x, int y) {
    int rootX = find(x);
    int rootY = find(y);
    if (rootX != rootY) {
        // Always make the smaller character the root
        if (rootX > rootY) {
            parent[rootX] = rootY;
        } else {
            parent[rootY] = rootX;
        }
    }
}

char* solution(char* s1, char* s2, char* baseStr) {
    // Initialize Union-Find
    for (int i = 0; i < 26; i++) {
        parent[i] = i;
    }
    
    // Union equivalent characters
    int len = strlen(s1);
    for (int i = 0; i < len; i++) {
        int c1 = s1[i] - 'a';
        int c2 = s2[i] - 'a';
        unionSet(c1, c2);
    }
    
    // Build result
    int baseLen = strlen(baseStr);
    char* result = (char*)malloc((baseLen + 1) * sizeof(char));
    
    for (int i = 0; i < baseLen; i++) {
        int charIdx = baseStr[i] - 'a';
        int root = find(charIdx);
        result[i] = root + 'a';
    }
    
    result[baseLen] = '\0';
    return result;
}

int main() {
    char s1[1001], s2[1001], baseStr[1001];
    fgets(s1, sizeof(s1), stdin);
    s1[strcspn(s1, "\n")] = 0;
    fgets(s2, sizeof(s2), stdin);
    s2[strcspn(s2, "\n")] = 0;
    fgets(baseStr, sizeof(baseStr), stdin);
    baseStr[strcspn(baseStr, "\n")] = 0;
    
    char* result = solution(s1, s2, baseStr);
    printf("%s\n", result);
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × α(26))

Union-Find operations are nearly constant time with path compression, where α is inverse Ackermann function

✓ Linear Growth

Space Complexity

O(26)

Union-Find parent array stores 26 characters

✓ Linear Space

32.4K Views

Medium Frequency

~25 min Avg. Time

856 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Union-Find (Optimal) — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler