Solution For Lexicographically Smallest Equivalent String

Problem Statement:

Given two strings A and B of equal length, we need to find the lexicographically smallest string C which has the same character set as A and B and is equivalent to A and B.

Solution:

The problem states that the strings A and B have the same length and we need to find the lexicographically smallest equivalent string with the same character set as A and B. So, we can apply a graph-based approach to solve this problem.

The basic idea is to create a graph using the characters in the strings A and B as nodes and the equivalent characters in the strings A and B as edges. Then we can perform a Depth-First Search (DFS) on the graph to find the lexicographically smallest equivalent string.

Algorithm:

1. Create an adjacency list for the characters in strings A and B. Each node in the adjacency list will contain a list of equivalent characters.

2. Traverse the adjacency list and perform a DFS on each unvisited node to find all the connected components.

3. For each connected component, sort the characters lexicographically and replace all the nodes with the lexicographically smallest node.

4. Finally, construct the equivalent string using the updated adjacency list.

Pseudo Code:

1. Initialize a visited array for all the characters in A and B.

2. Initialize an adjacency list for all the characters in A and B.

3. Populate the adjacency list with the equivalent characters from A and B. For each character in A and B, add the corresponding character from both strings to the adjacency list.

4. DFS on each unvisited node:

5. Mark the node as visited.
6. If the node has any equivalent nodes, perform DFS on each of them.
7. For each equivalent node, mark it as visited and add it to the connected component.

8. Update the connected component with the lexicographically smallest node.

9. Once all the connected components have been updated, construct the equivalent string:

10. For each character in A, find the corresponding node in the adjacency list and add the lexicographically smallest character to the result string.

Time Complexity:

The time complexity of this algorithm is O(n log n) where n is the length of the strings A and B. The DFS will be performed at most n times, and each DFS will take O(log n) time to sort the characters in the connected component.

Space Complexity:

The space complexity of this algorithm is O(n) to store the adjacency list and visited array.

Implementation:

Here is the Python implementation of the above algorithm:

class Solution:
def smallestEquivalentString(self, A: str, B: str, S: str) -> str:
# Initialize visited array for all the characters in A and B.
visited = [False] * 26

    # Initialize adjacency list for all the characters in A and B.
    adj_list = [[] for _ in range(26)]

    # Populate the adjacency list with the equivalent characters from A and B.
    for i in range(len(A)):
        x = ord(A[i]) - ord('a')
        y = ord(B[i]) - ord('a')
        adj_list[x].append(y)
        adj_list[y].append(x)

    # DFS on each unvisited node.
    def dfs(node, component):
        visited[node] = True
        component.append(node)
        for neighbor in adj_list[node]:
            if not visited[neighbor]:
                dfs(neighbor, component)

    # For each connected component, sort the characters lexicographically and replace all the nodes with the lexicographically smallest node.
    for i in range(26):
        if not visited[i]:
            component = []
            dfs(i, component)
            min_char = min(component)
            for node in component:
                visited[node] = True
                adj_list[node] = min_char

    # Construct the equivalent string using the updated adjacency list.
    result = ""
    for char in S:
        result += chr(ord('a') + adj_list[ord(char) - ord('a')])

    return result

Input:
A = “parker”, B = “morris”, S = “parser”

Output:
“paakar”

Step by Step Implementation For Lexicographically Smallest Equivalent String

/*

We can solve this problem with a union-find data structure. We can initialize each node in the union-find structure with a parent node of itself. Then, we can process each character in the input string, unioning the nodes corresponding to the current character and the previous character if they are not already unioned. Finally, we can use the find operation on the union-find structure to determine the parent node for each character in the input string. The parent node for the first character will be the lexicographically smallest equivalent string.

*/

class UnionFind {
    private int[] parent;
    
    public UnionFind(int n) {
        parent = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }
    
    public int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
    
    public void union(int x, int y) {
        int rootx = find(x);
        int rooty = find(y);
        if (rootx != rooty) {
            parent[rootx] = rooty;
        }
    }
}

class Solution {
    public String smallestEquivalentString(String A, String B, String S) {
        int n = A.length();
        UnionFind uf = new UnionFind(26);
        for (int i = 0; i < n; i++) {
            int x = A.charAt(i) - 'a';
            int y = B.charAt(i) - 'a';
            uf.union(x, y);
        }
        StringBuilder sb = new StringBuilder();
        for (char c : S.toCharArray()) {
            int x = c - 'a';
            int root = uf.find(x);
            sb.append((char) (root + 'a'));
        }
        return sb.toString();
    }
}

def smallestEquivalentString(A, B, S):
    # initialize the Union Find data structure with N components
    uf = UnionFind(len(A))

    # process each character pair
    for i in range(len(A)):
        # connect components containing character A[i] with B[i]
        uf.union(ord(A[i]) - ord('a'), ord(B[i]) - ord('a'))

    # convert string S to a list of characters
    S = list(S)

    # for each character in S, find its root and
    # replace it with the smallest equivalent character
    for i in range(len(S)):
        S[i] = chr(uf.find(ord(S[i]) - ord('a')) + ord('a'))

    # return the resulting string
    return "".join(S)

var smallestEquivalentString = function(A, B, S) {
    //Create a map to store all the characters in A and B
    let map = new Map();
    
    //Loop through A and B and store the characters in the map
    for(let i = 0; i < A.length; i++){
        let a = A[i];
        let b = B[i];
        
        //If the map doesn't have the character a, store it with the value of b
        if(!map.has(a)){
            map.set(a, b);
        }
        //If the map doesn't have the character b, store it with the value of a
        else if(!map.has(b)){
            map.set(b, a);
        }
        //Otherwise, we need to find the smaller character between a and b and 
        //store it in the map with the corresponding value
        else{
            let min = Math.min(a, b);
            let max = Math.max(a, b);
            map.set(max, min);
        }
    }
    
    //Create a variable to store the result
    let result = "";
    
    //Loop through S and find the corresponding character in the map
    for(let i = 0; i < S.length; i++){
        let s = S[i];
        //If the map has the character s, add it to the result
        if(map.has(s)){
            result += map.get(s);
        }
        //Otherwise, the character is already the smallest equivalent string,
        //so we can just add it to the result
        else{
            result += s;
        }
    }
    
    return result;
};

We can solve this problem with a DFS approach. We can start by initializing a visited array to keep track of which strings have been visited. We can also initialize an array to keep track of the equivalency class for each string. Then, we can do a DFS from the first string in the input array. For each string in the array, we can check if it has been visited. If it has not been visited, we can visit it and update the equivalency class for that string. We can also update the visited array so that we do not visit the same string multiple times. After we have visited all the strings in the array, we can return the equivalency class for the first string.

The time complexity of this algorithm is O(N * M), where N is the number of strings in the input array and M is the length of the longest string. The space complexity is O(N * M), since we need to store the visited array and the equivalency class array.

using System; 
using System.Collections.Generic; 
  
class GFG { 
      
// A class to represent a subset for union-find 
class subset 
{ 
    public int parent, rank; 
}; 
  
// A utility function to find set of an element i 
// (uses path compression technique) 
static int find(subset[] subsets, int i) 
{ 
    // find root and make root as parent of i (path compression) 
    if (subsets[i].parent != i) 
        subsets[i].parent = find(subsets, subsets[i].parent); 
  
    return subsets[i].parent; 
} 
  
// A function that does union of two sets of x and y 
// (uses union by rank) 
static void Union(subset[] subsets, int x, int y) 
{ 
    int xroot = find(subsets, x); 
    int yroot = find(subsets, y); 
  
    // Attach smaller rank tree under root of high rank tree 
    // (Union by Rank) 
    if (subsets[xroot].rank < subsets[yroot].rank) 
        subsets[xroot].parent = yroot; 
    else if (subsets[xroot].rank > subsets[yroot].rank) 
        subsets[yroot].parent = xroot; 
  
    // If ranks are same, then make one as root and increment 
    // its rank by one 
    else
    { 
        subsets[yroot].parent = xroot; 
        subsets[xroot].rank++; 
    } 
} 
  
// The main function that converts given array of strings 
// to an array of equivalence classes 
static void convert(string[] arr, int n) 
{ 
    // Create an empty equivalence class array 
    subset[] subsets = new subset[26]; 
  
    // Initialize all equivalence classes as single element 
    // sets 
    for (int i = 0; i < 26; i++) 
        subsets[i].parent = i; 
  
    // Consider every character and find their 
    // equivalence classes 
    for (int i = 0; i < n - 1; i++) 
    { 
        string s1 = arr[i]; 
        string s2 = arr[i+1]; 
  
        // Find length of the longest common prefix and 
        // print characters only if the longest common 
        // prefix is same as the shortest string 
        int len = Math.Min(s1.Length, s2.Length); 
        for (int j = 0; j < len; j++) 
        { 
            // If the characters are same, then same 
            // characters belong to same equivalence 
            // class. So union them. 
            if (s1[j] == s2[j]) 
            { 
                // consider every character and find 
                // their equivalence classes 
                int x = find(subsets, s1[j] - 'a'); 
                int y = find(subsets, s2[j] - 'a'); 
  
                // Union them 
                Union(subsets, x, y); 
            } 
  
            // Else print any string 
            else
                break; 
        } 
    } 
  
    // print all equivalence classes 
    for (int i = 0; i < n; i++) 
    { 
        string s = arr[i]; 
        for (int j = 0; j < s.Length; j++) 
            Console.Write((char)(find(subsets, s[j] - 'a') +  
                                  'a')); 
        Console.WriteLine(); 
    } 
} 
  
// Driver Code 
public static void Main() 
{ 
    string[] arr = {"geeksforgeeks", "geeks", 
                    "geek", "geezer"}; 
    int n = arr.Length; 
    convert(arr, n); 
} 
} 
  
// This code is contributed by rathbhupendra